Merge Sort

Algorithm description

The algorithm performs a bottom-up (i.e. non-recursive) merge sort.

Algorithm implementation

 1  subtype index is positive range 1..N;
 2  type sort_array is array(index) of integer;
 3
 4  procedure merge (
 5      arr: in out sort_array;
 6      lower, upper: integer;
 7      temp: in out sort_array;
 8      i: integer)
 9  is
10      enditem, list1, list2 : integer;
11  begin
12
13      -- calculate starting indices of (first) fields to be merged
14
15      list1 := lower;
16      list2 := lower+i;
17      if list2 > upper then
18          list2 := upper;
19      end if;
20
21      -- perform the merges
22
23      for j in 1..((upper-lower+1)/(i*2))+1 loop
24          enditem := list2+i-1;
25          if enditem > upper then
26              enditem := upper;
27          end if;
28
29          -- perform one merge
30
31          for k in list1..enditem loop
32              if arr(list1) <= arr(list2) then
33                  temp(k) := arr(list1);
34                  arr(list1) := integer'LAST;
35                  list1 := list1+1;
36              else
37                  temp(k) := arr(list2);
38                  arr(list2) := integer'LAST;
39                  list2 := list2+1;
40                  if list2 > enditem then
41                      list2 := enditem;
42                  end if;
43              end if;
44          end loop;
45
46          -- proceed to next fields
47
48          list1 := enditem+1;
49          list2 := list1+i;
50          if list2 > upper then
51              list2 := upper;
52          end if;
53      end loop;
54  end merge;
55  
56  procedure mergesort (arr: in out sort_array; lower, upper: integer)
56  is
57      temp: sort_array;
58  begin
59      discrete i := 1 in 1..upper-lower+1
60          new i := i*4
61      loop
62          merge (arr, lower, upper, temp, i);    -- merge arr -> temp
63          merge (temp, lower, upper, arr, i*2);  -- merge temp -> arr
64          i := i*4;
65      end loop;
66  end mergesort;

[ Sourcefile ]

Notes on design

Sorting is done by scanning through the array performing 1-by-1 merges to produce sorted sublists of size 2; then scan through the array performing 2-by-2 merges to produce sorted sublists of size 2, then do 4-by-4 merges to get sorted sublists of size 8, etc., until the whole list is sorted.

Once having implemented a merge procedure, the sorting is trivial: we only have to call the merge procedure with argument 1, 2, 4, 8, ... to perform the merges.

Example: 2, 1, 3, 9, 5, 6, 7, 4, 8, 10

merge with i=1:   2 | 1 | 3 | 9 | 5 | 6 | 7 | 4 | 8 | 10
merge with i=2:   1 , 2 | 3 , 9 | 5 , 6 | 4 , 7 | 8 , 10
merge with i=4:   1 , 2 , 3 , 9 | 4 , 5 , 6 , 7 | 8 , 10
merge with i=8:   1 , 2 , 3 , 4 , 5 , 6 , 7 , 9 | 8 , 10
merge with i=16:  1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10

In each loop execution, we perform 2 merges (lines 62 and 63, respectively) because of swaping source and destination arrays. This yields to i=i*4 instead of i=i*2 for the loop-variable of our discrete loop. Furthermore, an explicit check of the loop-variable has been omitted, which would suppress the execution of the second merge, when having already performed all the necessary merges. In this case, the second call to the merge procedure only copies the values from the temp array to the destination array.

Worst Case Performance

Mergesort requires

O( N log N )

comparisons to sort any file of N elements.

Furthermore, it uses extra space proportional to N (for the temporary array, used in the merging).

Selected Bibliography

[Bli94, section 3.2.2] [Ott93, p. 125] [Sed88, p. 163]

[ Samples Overview | Bibliography | WOOP Project ]