Merge sort is efficient, general-purpose sorting algorithm. Unlike bubble sort or insertion sort, it is usable in most practical cases. Merge sort is divide and conquer algorithm. Here we’ll see how to implement merge sort in C programming language. We’ll also analyze its performance in various conditions.

### Merge Sort Algorithm

Merge sort is divide and conquer algorithm.

- Repeatedly divide the input array into sub-arrays until each sub-array contains one element.
- Repeatedly merge the sub-arrays such that the merged the sub-array becomes sorted until there is one sub-array.

Step 1 is the divide part of the algorithm. At every stage, each sub-array will be divided into two parts. At the beginning, the whole array is the first sub-array that will be divided. If a sub-array contains even number of elements then the divided sub-arrays will also have equal number of elements. Otherwise, one divided sub-array will have one more element than the other divided sub-array. We’ll continue this process until all sub-arrays contain only one element. As the sub-arrays have one element, they are trivially sorted.

Step 2 is the conquer part, we’ll keep merging the sorted sub-arrays, such that the merged sub-arrays also be sorted. We’ll continue this process until we get only one sub-array which will contain all the elements of the starting array.

### Graphical Illustration of Merge Sort

The above diagram shows how merge sort works. The array has seven elements to begin with. First the array is divided into two sub-arrays, one with 4 elements and other with 3 elements. Then they further divided into four sub-arrays. And finally in the next stage, all sub-arrays have only one element. So, all sub-arrays are sorted (array with one element is always sorted). Divide part ends here and the conquer part begins. Single element sub-arrays are merged to become two element sorted sub-arrays. Similar process continues until all elements are merged into one sorted sub-array.

### Top-down Implementation of Merge Sort in C

Here is the top down implementation of merge sort in C. In top-down approach, the array is divided recursively into sub-arrays until the size of the sub-arrays becomes 1. Array of size size 1 is sorted by default. Then the sorted sub-arrays are merged continuously such that the merged sub-arrays become sorted. This process continues until all sub-arrays are merged into one array. Top down implementation of merge sort is more popular, widely used and easy to under stand method.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <stdio.h> void merge(int *arr, int start, int mid, int end) { int * tmp_arr = NULL; int i = 0; int l1 = start; int r1 = mid; int l2 = mid + 1; int r2 = end; tmp_arr = (int *)malloc(sizeof(int) * (end - start + 1)); while((l1 <= r1) && (l2 <= r2)) { if(arr[l1] < arr[l2]) tmp_arr[i++] = arr[l1++]; else tmp_arr[i++] = arr[l2++]; } while(l1 <= r1) tmp_arr[i++] = arr[l1++]; while(l2 <= r2) tmp_arr[i++] = arr[l2++]; for(i = start; i <= end; i++) arr[i] = tmp_arr[i - start]; free(tmp_arr); } void mergesort(int *arr, int start, int end) { int mid = 0; if(start < end) { mid = (start + end) / 2; mergesort(arr, start, mid); mergesort(arr, mid+1, end); merge(arr, start, mid, end); } } void main() { int arr[] = {54, 66, 31, 10, 4, 77, 32, 1, 56}; int i = 0; printf("Array before sorting: "); for (i = 0; i < (sizeof(arr)/sizeof(int)); i++) printf(" %d", arr[i]); printf("\n"); mergesort(arr, 0, sizeof(arr)/sizeof(int) - 1); printf("Array after sorting: "); for (i = 0; i < (sizeof(arr)/sizeof(int)); i++) printf(" %d", arr[i]); printf("\n"); } |

pppp

### Bottom-up Implementation of Merge Sort in C

In bottom-up approach, the arrays of size *n* is considered as *n* sub-arrays of size one. Then the sub-arrays are merged to together such that the merged sub-arrays become sorted. This process continues until the size of the merge sub-array becomes equal to the original array size *n*. Here is the bottom-up implementation of merge sort in C.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
void merge(int *arr, int start, int mid, int end) { int tmp_arr[100]; int i = 0; int l1 = start; int r1 = mid; int l2 = mid + 1; int r2 = end; while((l1 <= r1) && (l2 <= r2)) { if(arr[l1] < arr[l2]) tmp_arr[i++] = arr[l1++]; else tmp_arr[i++] = arr[l2++]; } while(l1 <= r1) tmp_arr[i++] = arr[l1++]; while(l2 <= r2) tmp_arr[i++] = arr[l2++]; for(i = start; i <= end; i++) arr[i] = tmp_arr[i - start]; } int min(int a, int b) { return (a < b)?a:b; } void mergesort(int *arr, int len) { int width = 0, i = 0; for (width = 1; width < len; width = width * 2) { for(i = 0; i < len; i = i + 2*width) { merge(arr, i, min(i + width, len), min(i + 2*width, len)); } } } |

ssss

### Performance of Merge Sort

Running time of merge sort in Big-O notation is *O(n log n)* for best, average and worst case scenarios. If we consider that merge sort take T(n) time to sort n number of elements, then the equation* T(n) = 2T(n/2) + n* follows the definition of the algorithm, where T(n/2) to sort the sub-array and n to merge two sorted sub-arrays. Applying master theorem, the running time in Big-O notation becomes *O(n log n)*.

Diagram below show an experimental result to demonstrate the performance of the merge sort for different types of input arrays. It shows how number of comparisons increases with the increase of number of inputs.

In this experiment we used three types of array. The numbers are randomly distributed in the first array, numbers are already sorted in the second array and numbers are reversely sorted in the third array. Number of inputs increase by 1000 in every iteration staring from 1000. The growth rate of comparisons required is *O(n log n)* in all cases but actual number of comparisons differs. In case of the random array, the number of comparisons is close to *n * log n*, where *n* is the number of inputs. But in case of already sorted array or reversely sorted array, the actual number of comparisons is close to *(n * log n ) / 2*. If the array is sorted, merge sort takes half number of comparisons compared to a random array.

I was Google around for content Sorting Algorithms in Objective – C this morning, when I came across your excellent page.

Great stuff!!

I just wanted to say that your page helped me a ton. I would have never found any deep insight article Sorting Algorithms in Objective – C. I specially like you how you add deep information on blog,

It helps to setup Sorting Algorithms in Objective

It’s funny: I recently published top online resources to learn Sorting Algorithms in Objective – C

Also, my tutorial might make a nice addition for learning sorting.

Either way, thanks. And have a great day!