Sorting on two dimensional processor arrays

A very simple algorithm for sorting two-dimensional arrays is shearsort [SchS 89]. It just sorts the rows and the columns of the array in turn. However, it has a time complexity of Θ(n log(n)), which is not optimal.

Algorithm

Algorithm shearsort

Input:

unsorted n×n-array

Output:

the array sorted in snake-like order

Method:

1. repeat log(n) times
1. sort the rows (in alternating direction);
2. sort the columns;
2. sort the rows (in the desired direction);

Sorting the rows in alternating direction means that even rows are sorted from left to right and odd rows from right to left.

Correctness

The correctness of shearsort is shown using the 0-1-principle [Knu 73]. The 0-1-principle states the following: If a comparator network sorts every sequence of 0's and 1's, then it sorts every sequence of arbitrary values. Without loss of generality, we may therefore restrict the proof to input sequences consisting of 0's and 1's.

After sorting the rows in the first step, there are n/2 rows that are sorted from left to right and n/2 rows that are sorted from right to left. When sorting the columns, every two of these rows are combined to at least one clean row (Figure 1). Thus, after the first iteration the array consist of some clean 0-rows, some clean 1-rows and an unsorted zone in between consisting of at most n/2 rows.

In the second iteration, every two rows of the unsorted zone are again combined to at least one clean row. Thus, after the second iteration the unsorted zone consists of at most n/4 rows, and so on.

After log(n) steps, there is at most one dirty row. In the additional last step this row is sorted, and the whole array is sorted.

Analysis

Sorting a row of length n with odd-even transposition sort takes n steps. Since the algorithm performs log(n) iterations, it requires n log(n) steps for row sorting plus n steps for the additional row sorting operation.

In each iteration, the height of the unsorted zone decreases by a factor of 2. This means that the columns contain an unsorted zone of decreasing length. Sorting a column that contains an unsorted zone of length k takes k steps of odd-even transposition sort. Therefore, the algorithm requires

n + n/2 + n/4 + ... + 2  =  2n – 2

steps for column sorting.

Altogether, shearsort has a time complexity of n (log(n) + 3) – 2  ∈  Θ(n log(n)) steps.

References

[Knu 73]   D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)

[SchS 89]   I.D. Scherson, S. Sen: Parallel sorting in two-dimensional VLSI models of computation. IEEE Transactions on Computers C-38, 2, 238-249 (1989)