Shear sort is a classical
algorithm used for sorting in
parallel on a
2D mesh. The basic idea is to lay out the elements on a 2D
array.
Assuming that the number of elements to be sorted N is a perfect square, we can place an element on every processor on an N-processor 2D mesh (with sqrt(n) rows and sqrt(n) columns).
The algorithm is thus: On odd time steps, we sort along the row, on even time steps, we sort along the column. When sorting along the row, we also consider the row number. If the row is odd-numbered, we sort left to right. If the row is even, we sort right to left.
The algorithm: for each row/column:
if odd(time) {
if odd(row) SortLeftToRight;
if even(row) SortRightToLeft;
} else {
SortTopToBottom;
}
Sorting along the row/column is equivalent to sorting on a single dimensional array, and thus will take O(sqrt(n)) time (see Odd-Even Transpose). It turns out that we only need to take O(log(n)) iterations for the whole list to be sorted. (the proof is left to the reader)
Thus this algorithm takes O(sqrt(n)log(n)) time.