Sorting on two-dimensional processor arrays

Shearsort

 up

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);

      sort the columns;

    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.

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 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.

combining two sorted rows to one clean row combining two sorted rows to one clean row
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)

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  element  Θ(n log(n)) steps.

Simulation

In the following simulation of shearsort a 32×32-array of 0's and 1's is sorted in row-major order. First, a random input is shown (click to start), and then the worst case is shown (click a second time).

 

(Java applet for the simulation of shearsort)

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)

 

Next:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 29.11.2004   Updated: 05.06.2016
Valid HTML 4.01 Transitional