Sorting on twodimensional processor arraysShearsort 
A very simple algorithm for sorting twodimensional 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 shearsort  
Input:  unsorted n×narray 
Output:  the array sorted in snakelike order 
Method: 

Sorting the rows in alternating direction means that even rows are sorted from left to right and odd rows from right to left.
The correctness of shearsort is shown using the 01principle [Knu 73]. The 01principle 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.
Definition: A row is called clean, if it consists of 0's only or 1's only, otherwise it is called dirty.
Definition: A maximal connected region along the sorting order that starts with a 1 and ends with a 0 is called an unsorted zone.
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 0rows, some clean 1rows 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.
 
Figure 1: Every two rows that are sorted in alternating direction are combined to at least one clean row (0's white, 1's gray)  
Sorting a row of length n with oddeven 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 oddeven 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.
In the following simulation of shearsort a 32×32array of 0's and 1's is sorted in rowmajor order. First, a random input is shown (click to start), and then the worst case is shown (click a second time).
[Knu 73]  D.E. Knuth: The Art of Computer Programming, Vol. 3  Sorting and Searching. AddisonWesley (1973)  
[SchS 89]  I.D. Scherson, S. Sen: Parallel sorting in twodimensional VLSI models of computation. IEEE Transactions on Computers C38, 2, 238249 (1989) 
Next: 
H.W. Lang Hochschule Flensburg lang@hsflensburg.de Impressum © Created: 29.11.2004 Updated: 05.06.2016 