4 The recursive version

The original merge sort algorithm works very well on files and linked lists. For files, although the algorithm requires the use of temporary storage that is the same size of the original file (to be sorted), it only uses sequential file access. This makes the algorithm very efficient with practically any storage media, including tapes!

The linked list implementation does not require any extra storage, as items are removed from one list and appended to another. It does require the ability to “peek” the value of the first item of each list. Nonetheless, the algorithm works very well on a linked-list implementation of queues.

The recursive version works well on arrays. However, it does require additional storage that is the same size of the array being sorted. There are different methods to accomplish this.

Listing 4 is the recursive version of merge sort.

 
1define sub mergesort 
2  by reference a : array 
3  by value b 
4  by value e 
5  local m 
6  m← ⌊⌋  
7  if m>b then  
8    invoke mergesort a↔a, b→b, m-1→e 
9  end if 
10  if m+1< e then  
11    invoke mergesort a↔a, m+1→b, e→e 
12  end if 
13  begin  
14    local i 
15    local j 
16    local k 
17    local x : array[b..e]  
18    i← b 
19    while i≤e do  
20      x[i]←a[i] 
21      i←i+1 
22    end while  
23    i←b 
24    j←m+ 1 
25    k←b 
26    while (i≤m)∨(j≤e) do  
27      if (i>m) then  
28        a[k]←x[j] 
29        j← j+1 
30      else if (j>e) then  
31        a[k]←x[i] 
32        i←i+1 
33      else if x[i]<x[j] then  
34        a[k]← x[i] 
35        i←i+1 
36      else  
37        a[k]←x[j] 
38        j←j+1 
39      end if 
40      k← k+1 
41    end while  
42  end 
43end define sub

Line 6 computes the mid point index of the portion of array a to be sorted by this invocation. The midpoint index is stored in local variable m.

The conditional statement starting on line 7 sorts the first half of the array, whereas the one starting on line 10 sorts the second half. Note that both recursive calls are protected because when b = m or m = e, we have the base case of having only one element in the array. Any array with only one element is sorted.

The block between line 13 and 41 merges the two smaller but now sorted chunks of the array. Local variable defined in this block are allocated only upon entry of this block, and deallocated as soon as the block completes.

Line 17 define the local variable x. Note that the index of the first element of x is b, and the index of its last element is e. Of course, you cannot do this in C or most programming languages, but it works in pseudocode.

Line 19 to 22 just copies a portion of array a into the local array x. This is necessary because we cannot merge two sub-arrays in place.

Line 26 is the loop that we use to merge the two sub-arrays. It exits when both chunks are used up (when i > m and j > e. The body of the loop is analyzed as follows:

• Line 27: if i > m, then the first chunk is empty, just copy from the second chunk.
• Line 30: if j > e, then the second chunk is empty, just copy from the first chunk.
• Line 33: if x[i] < x[j], then the first unused item of the first chunk is smaller, pick that one.
• Line 36: if x[i] ≥ x[j], then the first unused item of the second chunk is smaller or the same as the first unused item of the first chunk, pick from the second chunk.