Implementation
Let us implement merge sort in the C language.
We start by our main function, called “sort”,
void sort(int a[], int n)
{
// ...
}that takes as input an array “a” and its size, “n”.
As merge-sort is recursive, and recursive calls sort sub-ranges of the initial array, we need an auxiliary function “sort_range”:
void sort_range(int a[], int f, int n)
{
// ...
}that sorts a range of the array a given by the index of the first element, f, and the number of elements in the range, n.
The function “sort” then simply calls sort_range for the entire array:
void sort(int a[], int n)
{
sort_range(a, 0, n);
}As with any recursive function that terminates, sort_range must have a base case where recursion is not necessary anymore. The base case consists of ranges having 0 or 1 elements, as these ranges are already sorted:
void sort_range(int a[], int f, int n)
{
if (n <= 1) {
// nothing to do here
} else {
// ...
}
}In the recursive case, we need to do all the hard work. We need to split the range into two sub-ranges of roughly the same size and therefore we compute the lengths of the two sub-ranges:
void sort_range(int a[], int f, int n)
{
if (n <= 1) {
// nothing to do here
} else {
int n1 = n / 2;
int n2 = n - n1;
// ...
}
}We sort recursively the first sub-range:
void sort_range(int a[], int f, int n)
{
if (n <= 1) {
// nothing to do here
} else {
int n1 = n / 2;
int n2 = n - n1;
sort_range(a, f, n1);
// ...
}
}Once the first sub-range sorted, we sort the second one.
void sort_range(int a[], int f, int n)
{
if (n <= 1) {
// nothing to do here
} else {
int n1 = n / 2;
int n2 = n - n1;
sort_range(a, f, n1);
sort_range(a, f + n1, n2);
// ...
}
}Once the two sub-ranges sorted, we need to merge them together. We need a function “merge” that does this:
void merge(int a[], int f1, int n1, int f2, int n2)
{
// ..
}We finish off the “sort_range” function by calling merge for the two sub-ranges:
void sort_range(int a[], int f, int n)
{
if (n <= 1) {
// nothing to do here
} else {
int n1 = n / 2;
int n2 = n - n1;
sort_range(a, f, n1);
sort_range(a, f + n1, n2);
merge(a, f, n1, f + n1, n2);
}
}Going back to “merge”, we first allocate on the stack two temporary arrays.
void merge(int a[], int f1, int n1, int f2, int n2)
{
int t1[n1]; // uses C99 feature
int t2[n2];
// ...
}We are using here a language feature of the C language introduced in the standard C99 that allows us to declare variable-length arrays. Most compilers should support this. If you are using a compiler that is not C99 compliant, you should instead allocate t1 and t2 on the heap by using malloc (or the “new” operator in C++). Make sure you allocate them only once in “sort”, not at every call to “merge”, since heap allocation (malloc/new) is not a constant-time operation and could therefore affect run-time performance. In the case where you allocate t1 and t2 in the “sort” function, you need to either declare them as global variables, or, even better, pass them as additional parameters to sort_range and merge. You may also want to avoid stack allocation and use one of the variations presented above if your arrays are very large, in which case they might not fit into the stack.
We now copy the sub-ranges into the temporary arrays:
void merge(int a[], int f1, int n1, int f2, int n2)
{
int t1[n1]; // uses C99 feature
int t2[n2];
for (int i = 0; i < n1; ++i) {
t1[i] = a[f1 + i];
}
for (int i = 0; i < n2; ++i) {
t2[i] = a[f2 + i];
}
// ...
}We initialize the three pointers as discussed above:
void merge(int a[], int f1, int n1, int f2, int n2)
{
int t1[n1]; // uses C99 feature
int t2[n2];
for (int i = 0; i < n1; ++i) {
t1[i] = a[f1 + i];
}
for (int i = 0; i < n2; ++i) {
t2[i] = a[f2 + i];
}
int i = f1;
int j = 0;
int k = 0;
// ...
}We loop for as long as both pointers into the two sub-ranges are valid:
void merge(int a[], int f1, int n1, int f2, int n2)
{
int t1[n1]; // uses C99 feature
int t2[n2];
for (int i = 0; i < n1; ++i) {
t1[i] = a[f1 + i];
}
for (int i = 0; i < n2; ++i) {
t2[i] = a[f2 + i];
}
int i = f1;
int j = 0;
int k = 0;
while (j < n1 && k < n2) {
// ...
}
// ...
}We check which of the current elements in t1 and t2 is smaller and we add it to a.
void merge(int a[], int f1, int n1, int f2, int n2)
{
int t1[n1]; // uses C99 feature
int t2[n2];
for (int i = 0; i < n1; ++i) {
t1[i] = a[f1 + i];
}
for (int i = 0; i < n2; ++i) {
t2[i] = a[f2 + i];
}
int i = f1;
int j = 0;
int k = 0;
while (j < n1 && k < n2) {
if (t1[j] <= t2[k]) {
a[i] = t1[j];
i += 1;
j += 1;
} else { // t2[k] < t1[j]
a[i] = t2[k];
i += 1;
k += 1;
}
}
// ...
}As either j or k increases at each loop iteration, at some point one of them will point just past the end of the respective sub-range. This makes the while loop terminate.
At this point, one of the two sub-ranges has 0 elements left in it to be processed and the other sub-range has 1 or more elements. What remains to be done is to copy the non-empty sub-range into a. There is no need to check which one is non-empty, we can simply copy both of them, as copying the empty sub-range has no effect at all.
void merge(int a[], int f1, int n1,
int f2, int n2)
{
int t1[n1]; // uses C99 feature
int t2[n2];
for (int i = 0; i < n1; ++i) {
t1[i] = a[f1 + i];
}
for (int i = 0; i < n2; ++i) {
t2[i] = a[f2 + i];
}
int i = f1;
int j = 0;
int k = 0;
while (j < n1 && k < n2) {
if (t1[j] <= t2[k]) {
a[i++] = t1[j++];
} else { // t2[k] < t1[j]
a[i++] = t2[k++];
}
}
for (; j < n1; ++j) {
a[i++] = t1[j++];
}
for (; k < n2; ++k) {
a[i++] = t2[k++];
}
}Page 1 – Introduction
Page 2 – How it Works
Page 3 – Implementation
Page 4 – Time Complexity