Sorting on two dimensional processor arrays

The simplest algorithm for sorting two-dimensional arrays is 2d odd-even transposition sort. Unfortunately, it has a time complexity of Θ(n²), which is slow.

Idea

The idea of odd-even transposition sort is generalized to two-dimensional arrays in a straightforward way. Figure 1 shows the two steps of one-dimensional odd-even transposition sort that are repeated in alternating order.

In two-dimensional odd-even transposition sort, the elements are not just compared with their right and left neighbours, but also with their upper and lower neighbours. The sorting direction in the array is snake-like. Figure 2 shows the four steps of two-dimensional odd-even transposition sort that are repeated in round-robin order.

Figure 2: Two-dimensional odd-even transposition sort

Algorithm

In the following algorithm, with oets step a step of odd-even transposition sort is denoted.

Algorithhm 2d odd-even transposition sort

Input:

unsorted n × n-array

Output:

the array sorted in snake-like order

Method:

1. while the array is not sorted do
1. apply an odd oets step to the rows
2. apply an even oets step to the rows
3. apply an odd oets step to the columns
4. apply an even oets step to the columns

The sorting direction of the rows must be alternating, i.e. even rows from left to right and odd rows from right to left.

A simulation shows the crucial point of the algorithm: It sorts a random input of 0's and 1's remarkably fast. However, in the worst case, it is slow. Actually, the time complexity in the worst case is θ(n²), due to a behavior known as sand dune effect. The sand dune effect occurs also with random inputs of values drawn from a larger set than just the two values 0 and 1.