Sorting on twodimensional processor arrays2d oddeven transposition sort 
The simplest algorithm for sorting twodimensional arrays is 2d oddeven transposition sort. Unfortunately, it has a time complexity of Θ(n^{2}), which is slow.
The idea of oddeven transposition sort is generalized to twodimensional arrays in a straightforward way. Figure 1 shows the two steps of onedimensional oddeven transposition sort that are repeated in alternating order.
 
Figure 1: Onedimensional oddeven transposition sort  
In twodimensional oddeven 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 snakelike. Figure 2 shows the four steps of twodimensional oddeven transposition sort that are repeated in roundrobin order.
 
Figure 2: Twodimensional oddeven transposition sort  
In the following algorithm, with oets step a step of oddeven transposition sort is denoted.
Algorithhm 2d oddeven transposition sort  
Input:  unsorted n × narray 
Output:  the array sorted in snakelike order 
Method: 

The sorting direction of the rows must be alternating, i.e. even rows from left to right and odd rows from right to left.
In the following simulation of algorithm 2d oddeven transposition sort the input is an array of 0's (white) and 1's (gray). The simulation shows the crucial point of the algorithm: It sorts a random input of 0's and 1's remarkably fast (click on the array to start). However, in the worst case, it is slow (click again). Actually, the time complexity in the worst case is Θ(n^{2}), 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 (click again).
Next: [Shearsort] or 
H.W. Lang Hochschule Flensburg lang@hsflensburg.de Impressum © Created: 29.11.2004 Updated: 05.06.2016 