Sorting on two dimensional processor arrays

Algorithm 4-way mergesort

 German version  up

In practice, there is a need for an algorithm that is simple and easy to implement. In the following, the algorithm 4-way mergesort of Schimmler [Schi 87] is presented.

 

Algorithm

Definition:  An mtimesn-array of data is called roughly sorted, if sorting of the rows suffices to sort the array completely.

In a roughly sorted array each data element is already in its proper row. The idea of 4-way mergesort is to merge four roughly sorted k/2timesk/2-arrays to one roughly sorted ktimesk-array.

 

Procedure 4-way merge (k)
Input:ktimesk-array, whose four k/2timesk/2-subarrays are roughly sorted
Output:the roughly sorted ktimesk-array
Method:
  1. sort the rows of the subarrays:
    1. ascending in the upper subarrays,

      descending in the lower subarrays;

  2. sort the columns;
  3. sort the rows:
    1. odd rows ascending,

      even rows descending;

  4. sort the columns;

 

The correctness of procedure 4-way merge can be shown in an illustrative way by the 0-1-principle. (The 0-1-principle is also valid for the term "roughly sorted", since by subsequent sorting of the rows a sorted array can be obtained.)

Starting point is an array containing zeroes and ones, whose four subarrays are roughly sorted. In Figure 2(a) this situation is illustrated (zeroes are drawn white, ones gray).

Sorting the rows of the subarrays in step 1 results in a situation similar to Figure 2(b).

Sorting the columns in step 2 yields two roughly sorted ktimesk/2-arrays (Figure 2(c)).

After sorting the rows in alternating order in step 3 two different situations are possible: either the "dirty" halfrows (i.e. halfrows in which zeroes and ones occur) of situation (c) are in different halves (Figure 2(d)) or in the same half of the array (in the right half in Figure 2(e)). This depends on the number of full 1-halfrows in situation (c). In both cases however, sorting of the columns in step 4 leads to the situation shown in Figure 2(f), namely a roughly sorted ktimesk-array.

Proof of the correctness of procedure 4-way merge using the 0-1-principle
Figure 1:  Proof of the correctness of procedure 4-way merge using the 0-1-principle

By recursive application of procedure 4-way merge a totally unsorted array is roughly sorted:

 

Procedure roughsort (k)
Input:unsorted ktimesk-array
Output:roughly sorted ktimesk-array
Method:
  1. if k>1 then
    1. apply roughsort (k/2) to the four subarrays;
    2. 4-way merge (k);

 

An ntimesn-array is sorted by roughly sorting it and then sorting the rows:

 

Algorithm 4-way mergesort (n)
Input:unsorted ntimesn-array
Output:sorted ntimesn-array
Method:
  1. roughsort (n);
  2. sort the rows;

 

Following from the 0-1-principle algorithm 4-way mergesort sorts every ntimesn-array filled with arbitrary data, since it sorts all 0-1-arrays.

 

Analysis

Sorting a row or a column of length k with odd-even transposition sort takes k steps. In procedure 4-way merge this amounts to the following:

step 1: k/2 steps
step 2: ksteps
step 3: ksteps
step 4: k/2steps
altogether:   3ksteps

In step 4 only k/2 steps of odd-even transposition sort are necessary, since each column consists of two sorted subsequences shuffled into each other.

The recursive execution of 4-way merge in roughsort takes 3n + 3n/2 + 3n/4 + ... + 3 <= 6n steps. Thus, including n steps for the subsequent sorting of the rows 4-way mergesort has a time complexity of

T(n) <=7n

 

Simulation

The following applet shows how 4-way mergesort sorts a 32times32-array of 0's and 1's. For more clarity, operations that are performed in parallel on an ntimesn-processor array are shown sequentially here.

 

(Java applet for simulation of 4-way mergesort)

 

Conclusions

Algorithm 4-way mergesort for sorting an ntimesn-array has been presented. It has the same asymptotic complexity as the algorithm of Thompson/Kung [TK 77], namely O(n). Concerning the constant it is slower by a factor of about 2. However, its quality lies in its simplicity. An implementation of the algorithm on an instruction systolic array is given in [Schi 87] and in [Lan 90].

 

References

[Lan 90]H.W. Lang: Das befehlssystolische Prozessorfeld – Architektur und Programmierung. Dissertation, Christian-Albrechts-Universität Kiel (1990)
[Schi 87]M. Schimmler: Fast Sorting on the Instruction Systolic Array. Bericht Nr. 8709, Institut für Informatik, Christian-Albrechts-Universität Kiel (1987)
[TK 77]C.D. Thompson, H.T. Kung: Sorting on a Mesh-Connected Parallel Computer. Communications of the ACM, 20, 4, 263-271 (1977)

 

 

Next:   [Rotatesort]   or   up del.icio.us digg.com Google Ma.gnolia Mister Wong StumbleUpon YahooMyWeb LinkARENA

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 01.03.1997   Updated: 08.03.2013
Valid HTML 4.01 Transitional