C Programming

# Merge Sort in C

Many computer languages today have a general-purpose sort() function in the library. This function is used for commercial applications. Many programmers use the sort function provided by the language library whenever they need a sort function.

The mergesort program, written normally, is comparable (in terms of speed) to the sort() function provided by C++ in its algorithm library. Merge-sort is also a general purpose commercial program.

This article explains how to write the mergesort program in the C language.

## Divide-and-Conquer Algorithm, in its Broad Sense

In its broad sense, the array of elements are divided into two halves: the left half and the right half. If the total number of elements to be sorted is odd, then the left half is made bigger than the right half, by 1 unit. Otherwise, both halves are of the same length. The two halves are then merged while sorting to form one sorted array. The merging/sorting is conquering. Consider the following characters to be sorted:

Q W E R T Y U I O P

Dividing this set of alphabetic characters into two halves, gives:

Q W E R T Y U I O P

A sub array is called a run. So the left sub array, “Q W E R T” is a run and the right sub array, “Y U I O P” is also a run. A run can also have only one element.

Merging/sorting (conquering) both halves into one set gives:

E I O P Q R T U W Y

The code to divide by 2 is:

int iMiddle = (iBegin + iEnd) / 2;

This is integer division. So, the whole number part of the result is taken. With this, if the total number of elements in the set is odd then the left half would be bigger than the right half,by 1 unit for zero based indexing.

For the above statement and the set, {‘Q’, ‘W’, ‘E’, ‘R’, ‘T’, ‘Y’, ‘U’, ‘I’, ‘O’, ‘P’}, iBegin = 0, iEnd = 10 (which is last index of 9, plus 1), iMiddle = 5;

The code to merge/sort (conquer) is:

int i = iBegin;
int j = iMiddle;
for (int k = iBegin; k <iEnd; k++) {
if (i= iEnd || P[i] <= P[j])) {
Q[k] = P[i];
i = i + 1;
} else {
Q[k] = P[j];
j = j + 1;
}
}

P is the given array. Q would have the sorted array, in this case.

If this code is applied to the set, {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'}, there will be merging of the divided halves, but no sorting (because each element in the left run is less than ‘Y’). This code is revisited below to show its effectiveness in sorting a consecutive pair of runs.

## Practical Divide-and-Conquer Algorithm

The whole mergesort program can be written top-down or bottom-up. In this article, the program is written, top-down.

A mergesort operates conceptually in the following way:

1) Divide the unsorted set into N subsets (runs), where each has one element. Note that a set with only one element is considered sorted.

2) Repeatedly merge subsets to obtain new sorted subsets, until only one subset is left. This is the sorted set.

With these two points, a given unsorted set is divided into two runs. Each of these two runs are recorded in memory for merging/sorting together, but not merged or sorted yet. Each run again on either side, is divided into two. The consecutive pairs of runs are recorded for merging/sorting together, but not merged or sorted still yet. This division into two and recording for merging/sorting of consecutive pairs are repeated until there is only one element per run.

The recording into memory for merging/sorting together of consecutive runs is done by calling the above sorting code recursively after division. The sorting code is in a separated function. The division statement and the calling of the sorting function (which also does merging) is in one code segment (one function) with the division statement typed first.

When the division has reached the state of single element runs, the merging/sorting functions recorded in memory are called in reverse order in which they were recorded. It is one merge/sort function that was recorded in memory many times with different arguments. Consecutive pairs of single elements are first sorted, merging at the same time. The sorting and merging of consecutive runs continue until the whole set is sorted. So, the sorting is not really on the arrangement of elements as was given originally.

In C, there is a need for a second array, whose length is as long as the given array. Initially, all the elements for this second array has to be made, the default value of the data type. The elements of the given array are sorted into this second array. Then copied back to the given array, overriding the unsorted elements.

For characters, this second array can be created and initialized as follows:

char P[] = {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'};
int sz = sizeof(P)/sizeof(P[0]);
char Q[sz];
for (int i=0; i<sz; i++)
Q[i] = ' ';

Here, the given array is P, and the second array is Q. This code can be in the main function. In C/C++ the default character is '' and not a space (' '). However, since the g++ compiler would not allow the assignment of '' to Q[i], the single space (' '), was assigned.

Note that the default values for array Q elements are not really necessary for the complete mergesort program as they will still be overridden by the elements of interest. Declaring array Q with its size, sz suffices.

The set, {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'}, is used to explain how mergesort is achieved practically, in this section. Giving array Q default values has been taught in this article as extra knowledge.

The set is divided into the two sets:

{'Q', 'W', 'E', 'R', 'T'} and {'Y', 'U', 'I', 'O', 'P'}

The above merging/sorting code is called as a function but sorting and merging do not take place. In the real program, the sorting and merging of these two runs are recorded in memory, first. The sorting and merging will not ultimately necessarily be done on these two particular arrangement of characters.

The above two subsets are each, further divided into two to have:

{'Q', 'W', 'E'} and {'R', 'T'} and {'Y', 'U', 'I'} and {'O', 'P'}

Note that for each new division here, the left subset is longer than the right subset by one unit.

The above merging/sorting code is called as a function, for consecutive pairs of these new subsets. But sorting and merging does not take place immediately. The sorting and merging of these consecutive pairs of runs are recorded in the computer’s memory. The sorting and merging will not ultimately, necessarily be done, on the particular arrangement of characters of these consecutive pairs of runs.

The above subsets are each, further divided into two to have:

{'Q', 'W'} and {'E'} and {'R'} and {'T'} and {'Y', 'U'} and {'I'} and {'O'} and {'P'}

The sorting and merging of consecutive pairs is recorded.

Here, some subsets cannot be divided any more because they each consists of one element. Then, division of the more than one length subsets above, lead to:

{'Q'} and {'W'} and {'E'} and {'R'} and {'T'} and {'Y'} and {'U'} and {'I'} and {'O'} and {'P'}

The sorting and merging of consecutive pairs is recorded.

The sorting and merging function is coded in a recursive manner. And so, it will be called in the reversed order, for the many times, it was recorded.

So, {'Q'} and {'W'} will be sorted and merged into {'Q', 'W'}. {'E'} and {'R'} will be sorted and merged into {'E', 'R'}. {'T'}. {'Y'} will be sorted and merged into {'T', 'Y'}. {'U'} and {'I'} will be sorted and merged into {'I', 'U'}. {'O'}. {'P'} will be sorted and merged into {'O', 'P'}. The above merge and sort function is used here; and it is used throughout.

Next: {'Q', 'W'} and {'E', 'R'} will be sorted and merged into {'E', 'Q', 'R', 'W'}. {'T', 'Y'} and {'I', 'U'} will be sorted and merged into, {'I', 'T', 'U', 'Y'}. At this stage, {'O', 'P'} is not joined with any previous subsets of two. The above merge and sort function has been used here and is used throughout.

The next stage: {'E', 'Q', 'R', 'W'} and {'I', 'T', 'U', 'Y'} are sorted and merged into {'E', 'I', 'Q', 'R', 'T', 'U', 'W', 'Y'}. At this stage, {'O', 'P'} again is not joined with any of the previous subsets.

The last stage: {'E', 'I', 'Q', 'R', 'T', 'U', 'W', 'Y'} and {'O', P'} are sorted and merged into {'E', 'I', 'O', 'P', 'Q', 'R', 'T', 'U', 'W', 'Y'}. The unsorted set has been sorted.

## Coding mersort in C

The task is to sort array P and not array Q. So, for the whole mergesort program, array Q is first made a copy of array P. The program then sorts array Q into array P. This is not quite what is insinuated above. There are four functions for the complete mergesort program.

## The function to Divide and Merge

This is the principal function in the program. Recall that merging also involves sorting of the left and right consecutive runs. This merging is in memory and actually begins when the array has been divided by two and two and two etc. until there is only one element per run. So, sorting and merging begins at that stage with a pair for one element per run. The skeleton of the sorting function is:

void topDownSplitMerge(char Q[], int iBegin, int iEnd, char P[]) {
|                    |
// divide the subset longer than 1 element into two
int iMiddle = (iBegin + iEnd) / 2;              // iMiddle is the mid point
|                    |
|                    |
|                    |
// merge the resulting subsets from array Q[] into P[]
topDownMerge(Q, iBegin, iMiddle, iEnd, P);
}

This function takes the given array as Q which in this case is actually the copy array Q. It also takes the copy array as P which in this case is actually the given array P. For the first call of this function, iBegin = 0 and iEnd = N, where N is the size of both arrays. These are because of the zero-indexed employment of the array.

After a division by two, iBegin will be the first index of the left run and iEnd will be the last index of the consecutive right run. Division by two gives the integer, iMiddle, ignoring the remainder. This is the last index of the left run and also the first index of the right run. This ambiguity is eliminated by the while-condition of the sorting code.

The last statement in the code above is a call to the precise merge and sort function. This call goes to the memory, when called. It will be executed in reversed order for all its calls because it is a recursive call. It takes the variables as arguments. Q, iBegin, iEnd, and P, received by the outer coded function. iMiddle, which is also one of its arguments, is created inside the outer coded function, above the call.

It is inside this outer coded function that the left and right runs have to be identified (divided). This is best done by making a recursive call to the outer coded function as follows (some code included into function definition):

void topDownSplitMerge(char Q[], int iBegin, int iEnd, char P[]) {
// divide the subset longer than 1 element into two
int iMiddle = (iBegin + iEnd) / 2;              // iMiddle is the mid point

// recursively sort both runs from array A[] into B[]
topDownSplitMerge(P, iBegin, iMiddle, Q);  // divide left subset into two for sorting, after memorization
topDownSplitMerge(P, iMiddle, iEnd, Q);  // divide right subset into two for sorting, after memorization
// merge the resulting subsets from array Q[] into P[]
topDownMerge(Q, iBegin, iMiddle, iEnd, P);
}

The two new recursive calls have been typed above the topDownMerge() recursive call. These two calls will be memorized along with topDownMerge() and called as many times as necessary, each in reverse order.

If the given array has no element, there should be no sorting. If the number of elements in the given array, is 1, then the array is already sorted, and no sorting should take place. This is taken care of by one statement inside but at the top of the outer coded function, topDownSplitMerge() as follows:

void topDownSplitMerge(char Q[], int iBegin, int iEnd, char P[]) {
if (iEnd - iBegin<= 1)
return;

int iMiddle = (iBegin + iEnd) / 2;

topDownSplitMerge(P, iBegin,  iMiddle, Q);
topDownSplitMerge(P, iMiddle,    iEnd, Q);
topDownMerge(Q, iBegin, iMiddle, iEnd, P);
}

## The precise Function to Merge and Sort

The name of this function is topDownMerge(). It is called recursively by topDownSplitMerge(). The code is:

void topDownMerge(char P[], int iBegin, int iMiddle, int iEnd, char Q[]) {
// While there are elements in the left or right subsets...
int i = iBegin;
int j = iMiddle;
for (int k = iBegin; k <iEnd; k++) {
if (i= iEnd || P[i] <= P[j])) {
Q[k] = P[i];
i = i + 1;
} else {
Q[k] = P[j];
j = j + 1;
}
}
}

In theory, this function iterates from the beginning of the left run (subset) to the end of the right run (subset). Note how the ambiguity mentioned above has been taken care of by the while-condition of the if-construct.

## Doing One-Time Copy for all the Elements

At the beginning of the program, after the function below (this section), has been called, all the elements of the given array have to be copied to the array, Q. The code for that is:

void copyArray(char P[], int iBegin, int iEnd, char Q[]) {
for (int i = iBegin; i<iEnd; i++)
Q[i] = P[i];
}

It is called once from the following function. This takes as arguments, the given array, P, then 0, then N, and the other array Q, which is in theory empty but already has the same number of elements as P. iEnd, which is the same as N, here, is the length of the originally given array.

## Function to Kick-start the Program

The function to kick-start the program is:

void topDownMergeSort(char P[], char Q[], int N) {
copyArray(P, 0, N, Q);           // P[] is copied to Q[] once
topDownSplitMerge(Q, 0, N, P);
}

It calls the copyArray() function, with the expected arguments. It calls next the principal function, topDownSplitMerge(), with the positions of the arrays, P and Q, swapped. This is why, in the topDownMerge() code, sorted values are sent to Q and not to P.

## Code Arrangement

If the above four coded functions, are typed in the following order,

– void topDownMerge()

– void topDownSplitMerge()

– copyArray()

– topDownMergeSort()

then the mergesort program (consisting mainly of these four functions) will work in a C compiler without any problem.

## C Main Function

A suitable C main function for this program is:

int main(int argc, char **argv)
{
char P[] = {'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P'};
int sz = sizeof(P)/sizeof(P[0]);
char Q[sz];
for (int i=0; i<sz; i++)
Q[i] = ' ';
topDownMergeSort(P, Q, sz);

for (int i=0; i<sz; i++)
printf("%c ", P[i]);
printf("\n");

return 0;
}

## Conclusion

Divide and conquer algorithm divides the problem into smaller pieces, with the hope of solving them independently. After all the smaller pieces have been solved, their solutions are combined into one main solution. With merge-sort, there is continuous division by two, until each subset is one element long, and automatically already sorted. Bringing these single element runs together, involves recursive functions and actual sorting, beginning with pairs of single elements.