Mergesort Files: sort.c, sort.h Mergesort, and sorts an array, a[], by repeatedly exchanging array elements until they are sorted. Mergesort is described below using pseudo-code: mergesort(p, q) { if p < q { m = (p+q) div 2; mergesort(p, m) mergesort(m+1, q); merge(p, m+1, q+1); } } /* merge merges the two sorted array regions a[p .. r-1] and a[r .. q-1] to * give the sorted array region a[p .. q-1]. */ merge(p, r, q) { i = p; j = r; k = p; /* merge while both array regions have at least 1 element left top scan. */ while i < r and j < q { if a[i] <= a[j] { b[k] = a[i]; i = i + 1; } else { b[k] = a[j]; j = j + 1; } k = k + 1; } /* Add any remaining elements from array region 1 to the merge result. */ while i < r { b[k] = a[i]; i = i + 1; k = k + 1; } /* Add any remaining elements from array region 2 to the merge result. */ while j < q { b[k] = a[j]; j = j + 1; k = k + 1; } /* Copy merge result over the old array entries. */ for k = p to q-1 { a[k] = b[k] } } main program { mergesort(1, n); } The above algorithm shows mergesort implemented recursively. Mergesort sorts an array by splitting it into two regions and sorting each using recursive calls to mergesort. The two sorted array regions are then merged together. Recursion proceeds deeper until mergesort() is called on an array region of just one element. The file sort.c contains slightly different mergesort implementations, which will be explained later. For now, explanation will be given using the mergesort0 functions as these are most like the above pseudo code. The mergesort algorithm is implemented in the function mergesort0_recursive(). The merge code is contained within mergesort_recursive0(), rather than a separate function. Programs can call the function mergesort0() which in turn calls mergesort0_recursive(), after setting up global variables that mergesort0_recursive() accesses. Global variables for the array element size, comparison function, and the temporary array are used. There are several options when implementing mergesort. To store the merge result, a temporary array is used. In the above pseudo-code algorithm, the temporary array stores the merge result, and is copied over old array entries when merging is completed. This array copy that occurs after each merge can be avoided by alternating between the two arrays when calling mergesort(). In the file sort.c the function mergesort0() and mergesort0_recursive() implement mergesort using array copying. The functions mergesort() and mergesort_recursive() use the quicker array alternating method. The array alternating version requires an additional parameter in mergesort_recursive(). This parameter points to the start of the destination array region, where the sorting result will be placed. When mergesort() is called it sets up a temporary array, swap_array[], and initialises array elements to the same values as the array being sorted, base[]. Then mergesort_recursive() is called with the swap_array[] as the region to be sorted, and base[] as the destination. As recursive calls to mergesort_recursive() occur, the source and destination pointers alternate between the two arrays. Another option when implementing mergesort is to use iteration rather than recursion.