Average case analysis of five two-dimensional bubble sorting algorithms
Serap A. Savari · 1993
For each of five generalizations of the odcl-even transposition sort to a sorting algorithm on a /77X W mesh of processors.we demonstrate that with "high probability," the number of steps required to sort a random permutation of N numbers is @(N).1