Merge Sort in C – Algorithm and Program With Explanation

Merge Sort in C

Hackr.io.

Merge sort is one of the most powerful sorting algorithms. Merge sort is widely used in various applications as well. The best part about these algorithms is that they are able to sort a given data in O(nLogn) complexity as against O(n2) complexity (we will soon see how) of bubble sort and selection sort. Moreover, merge sort is of interest because it creates an excellent case study for one of the widely used techniques in Computer Science – divide and conquer.

Merge Sort Algorithm – Explanation

Given an array of length, say n, we perform the following steps to sort the array:

  1. Divide the array into 2 parts of lengths n/2 and n – n/2 respectively (here if n is odd, we round off the value of n/2). Let us call these arrays as left half and right half respectively.
  2. Recursively sort the left half array and the right half array.
  3. Merge the left half array and right half-array to get the full array sorted.

Let us take an example:

Given Array: [6, 4, 5, 1, 2, 7, 3]

First, as per step 1 above, we divide the array into 2 parts. As we can see, the following are the subarrays left half and right half:

  • Left half: [6, 4, 5, 1]
  • Right half: [2, 7, 3]

Then, as per step 2 above, we recursively sort the left and right halves. Here is how the sorted subarrays will look like:

  • Recursively sorted left half: [1, 4, 5, 6]
  • Recursively sorted right half: [2, 3, 7]

Finally, as per step 3, we will merge these 2 halves to create the final sorted array. Final merged and sorted array: [1, 2, 3, 4, 5, 6, 7]

The left and the right halves can always be sorted recursively using the same algorithm. The magic happens in creating the final merged and sorted array. So, let us understand it well using the above example.

In the above example, we are given 2 arrays [1, 4, 5, 6] and [2, 3, 7]. We are supposed to merge these 2 arrays into a single sorted array. Let us place a pointer at the head of each array. We will depict the pointer by underlining the corresponding element where the pointer points to.

Final merged array = []

Left array: [1, 4, 5, 6]

Right array: [2, 3, 7]

As can be seen, the pointer of the left array is at 1 and the pointer of the right array is at 2. We pick the smaller one and put it in the final merged array and move the corresponding pointer. After doing this, we will have the following state:

Final merged array = [1]

Left array: [4, 5, 6]

Right array: [2, 3, 7]

Here the pointers are now at 4 and 2 respectively. We again do what we did above – pick the smaller one and put it in the final merged array and move the corresponding pointer. We will get the following:

Final merged array = [1, 2]

Left array: [4, 5, 6]

Right array: [3, 7]

We repeat this again to get:

Final merged array = [1, 2, 3]

Left array: [4, 5, 6]

Right array: [7]

Continuing this exercise, we can see that we are successfully able to get the final merged array in the sorted form:

Final merged array = [1, 2, 3, 4, 5, 6, 7]

Left array: []

Right array: []

So, as can be seen, we started with an unsorted array and we were successfully able to get a sorted array. Another question that is to be answered – how were the left and the right arrays sorted? Well, we sorted them recursively using the same technique as above. For instance, consider the right array: [2, 7, 3]. To sort it, we will break it again into 2 sub-arrays: [2, 7] and [3]. Both these sub-arrays are already sorted so we can simply merge them by using the technique explained above to get the sorted array [2, 3, 7].

Take a look at the following image to understand how this same procedure is recursively applied on the subarrays:

In the above image, we’ve shown the actual subarray in black and the resultant sorted subarray in blue. Let us understand the detailed steps involved in performing a merge sort in the above array:

  • [6, 4, 5, 1, 2, 7, 3] is divided into [6, 4, 5, 1] and [2, 7, 3]
  • [6, 4, 5, 1] is divided into [6, 4] and [5, 1]
  • [6, 4] is divided into [6] and [4]
    • [6] is a single element array and so, is sorted.
    • [4] is a single element array and so, is sorted.
  • [6] and [4] are merged into [4, 6]
  • [5, 1] is divided into [5] and [1]
    • [5] is a single element array and so, is sorted.
    • [1] is a single element array and so, is sorted.
  • [5] and [1] are merged into [1, 5]
    • [4, 6] and [1, 5] are merged into [1, 4, 5, 6]
  • [2, 7, 3] is divided into [2, 7] and [3]
  • [2, 7] is divided into [2] and [7]
    • [2] is a single element array and so, is sorted.
    • [7] is a single element array and so, is sorted.
  • [2] and [7] are merged into [2, 7]
  • [3] is a single element array and so, is sorted.
  • [2, 7] and [3] are merged into [2, 3, 7]
  • [1, 4, 5, 6] and [2, 3, 7] are merged into [1, 2, 3, 4, 5, 6, 7]

Observe one important point – we need a separate array in order to store the data of the final merged array. This means that merge sort requires additional space.

So, that’s how merge sort works. Here is an animation that explains the same.

Merge Sort Pseudo Code

Before we get into the actual code, let us take a look at the pseudo code.

function merge_sort(i, j, a, aux) {
    mid = (i + j) / 2
    merge_sort(i, mid, a, aux)
    merge_sort(mid + 1, j, a, aux)
    pointer_left = i, pointer_right = mid + 1
    for k in [i ... j] {
        if pointer_left points to smaller element, aux[k] = a[pointer_left] and increment pointer_left by 1
        if pointer_right points to smaller element, aux[k] = a[pointer_right] and increment pointer_right by 1
    }
    copy the contents of aux[i .. j] to a[i .. j]
}

Now, let us take a look at the actual working code.

Merge Sort Program in C

Let us understand the code step-by-step:

void merge_sort(int i, int j, int a[], int aux[])

This prototype means that the merge_sort function sorts the sub-array a[i .. j] using auxiliary array aux[].

if (j <= i) {
    return;
}

if j <= i, clearly, the subarray a[i .. j] contains either 1 element (which is sorted) or no elements (which is also sorted). So, we do nothing in this case and simply return.

int mid = (i + j) / 2;

We plan to partition the array into 2 sub-arrays of almost equal lengths. These subarrays are a[i .. mid] and a[mid + 1 .. j]. Clearly, mid = (i + j) / 2 is the best here since mid is the average of i and j.

  merge_sort(i, mid, a, aux);
  merge_sort(mid + 1, j, a, aux);

Here, we are recursively sorting a[i .. mid] and a[mid + 1 .. j] sub-arrays by calling the same merge_sort function.

Once we have these 2 sorted subarrays in place, the rest of the code simply merges the 2.

  int pointer_left = i;
  int pointer_right = mid + 1;
  int k;

Here, we place pointer_left at the beginning of the left sub-array a[i .. mid] and the pointer_right at the beginning of the right subarray a[mid + 1 .. j].

  for (k = i; k <= j; k++) {
    if (pointer_left == mid + 1) {
        aux[k] = a[pointer_right];
        pointer_right++;
    } else if (pointer_right == j + 1) {
        aux[k] = a[pointer_left];
        pointer_left++;
    } else if (a[pointer_left] < a[pointer_right]) {
        aux[k] = a[pointer_left];
        pointer_left++;
    } else {
        aux[k] = a[pointer_right];
        pointer_right++;
    }
}

Here, we have 4 cases:

  1. pointer_left == mid + 1: in this case, the left subarray is finished and all of its elements have already been merged.
  2. pointer_right == j + 1: in this case, the right subarray is finished and all of its elements have already been merged.
  3. a[pointer_left] < a[pointer_right]: here, none of the 2 arrays have finished. However, the pointer_left points to a smaller element than pointer_right and so, we put that in the merged array.
  4. else the last case: here, none of the 2 arrays have finished. However, the pointer_right points to a smaller element than pointer_left and so, we put that in the merged array.

Finally, we copy the elements from aux[] to a[].

for (k = i; k <= j; k++) {
    a[k] = aux[k];
}

So, that’s how merge sort works.

Merge Sort Complexity

Complexity gives a rough idea of the time taken to execute the algorithm as a function of the size of the input. For instance, let T(n) be the time taken to perform merge sort on an array of size n.

As we can see, that T(n) comprises of 3:

  1. Time spent in performing merge sort on the left half. The left half is of size n/2 and so, the time spent would be nothing but T(n/2).
  2. Time spent in performing merge sort on the right half. The right half is of size n/2 and so, the time spent here would also be T(n/2).
  3. Time spent in merging the left and the right halves. As we can see, to merge the 2 halves, we place pick each element one-by-one from the 2 subarrays and fill in the original array. Since there are n elements, the time taken in merging would be proportional to n. So, let us call this time as cn where c is some constant.

Total time, T(n) = T(n/2) + T(n/2) + cn

So, we have the equation as: T(n) = 2T(n/2) + cn. With some maths, this equation can be solved as

T(n) = 2T(n/2) + cn

     = 2(2T(n/4) + cn/2) + cn = 22T(n/22) + 2cn

     = 2(2(2T(n/8) + cn/4) + cn/2) + cn = 23T(n/23) + 3cn

     …

     …

The k-th term of the above series is: 2kT(n/2k) + kcn

Put 2k = n, we have k = log2n. We put this value of k in the equation above to get: T(n) = nT(1) + cnlog2n

Here, T(1) and c are constants. So, we can write T(n) = An + Bnlog2n. Since the term nlog2n is larger than n, we can see that nlog2n is the dominant term. Just to give you an idea, when n = 232, nlog2n = 32 * 232, which is clearly an order of magnitude larger. So, T(n) can be written as T(n) = O(nlog2n).

The complexity of bubble sort algorithm on the other hand as we saw was O(n2). Clearly, merge sort is much faster than bubble sort algorithm and that’s why it is widely used in various applications and libraries.

Conclusion

Merge sort is an interesting algorithm and forms a great case-study to understand data structures and algorithms. In order to develop strong foundations in computer science, you are advised to thoroughly understand various sorting algorithms which will help you pick up the basics.

PS: You might be interested in our Bubble Sort in C blog post as well.

Related Posts

46 Comments, RSS

  1. James Cooper November 1, 2018 @ 2:06 pm

    What is merge sort definition?

    • Delia Roy November 14, 2018 @ 3:01 am

      Merge sort is an algorithm to sort an array. It is based on divide and conquer technique which sort an array in O(n logn) time. This is known as its worst-case time complexity. Merge sort first divide the whole array into equal halves and then combined them in a sorted manner. This is very simple algorithm.

  2. Tom Collins November 1, 2018 @ 3:42 pm

    Is insertion sort better than merge sort?

    • Nina Chavez November 14, 2018 @ 3:03 am

      Merge sort is preferred when there is a large scale of numbers to be sort. Otherwise, insertion sort is faster than any other. Merge sort applies divide and conquer the whole list and then combine them in the order. Whereas, insertion sort is a simple sorting algorithm that builds the final sorting array one item at a time.

  3. Jason Emery November 1, 2018 @ 3:44 pm

    How can I see merge sort visualization?

    • Hackr Team

      Hackr Team November 1, 2018 @ 5:00 pm

      If you want to see Merge sort in a visual format then we can include an image depicting merge sort and merge sort animation as well in form of a gif. Is that what you want or is there anything we are missing?

  4. Nigel Bright November 1, 2018 @ 3:45 pm

    Where can I get a working openGL code for a merge sort in C?

    • Antoinette Montgomery November 14, 2018 @ 11:23 am

      OpenGL is cross platform API for rendering 2D and 3D vector graphics. This has set of functions which are used by the client program. For example GL_COLOR_BUFFER_BIT, it is used to display.
      You can refer some trusted websites like github, codeproject etc. where openGL codes are available with the demonstration.

  5. Ian Jenkins November 1, 2018 @ 3:46 pm

    Is merge sort stable?

    • Lorraine Ford November 14, 2018 @ 11:39 am

      Yes, definitely merger sort is a stable sorting algorithm. Even in an efficient implementation. Just make sure “L(i) <= R” when you are applying merge sort on two halves. Because stability depends on how you properly implement the sort operation. When determining the sort order, only part of the data is examined.

  6. Philip Harbour November 1, 2018 @ 3:47 pm

    Why Quicksort is better than merge sort?

    • Stanley Park November 14, 2018 @ 11:49 am

      We can’t say Quicksort is better than merge sort. Yes, it is better for a different kind of application. Both Quicksort and Merger sort have worst-case and take O(nlogn) time for sorting. While sorting, the most important characteristic is the easy implementation of sequential access. Quicksort is usually faster than merge sort and merge sort is more stable than quicksort. So use the algorithm that suits your need.

  7. Donald Morrison November 1, 2018 @ 3:47 pm

    What is the difference between quicksort and merge sort?

    • Maggie Kelley November 14, 2018 @ 12:10 pm

      • Both are based on the divide and conquer technique.
      • In Quicksort there is no necessity to divide the list into a half, whereas in merger sort list is always divide into half.
      • Quicksort is used for the small size of an array and merge sort can be applied to any type of array.
      • Worst-case complexity of Quicksort is O(n^2) and of merge sort is O(n log n).
      • Merge sort is more efficient than Quicksort.
      • Sorting method used for Quicksort is internal and for Merge sort is external.
      • Last but not the least Quicksort is faster for small data set and consistent speed in all type of data set.
  8. Paul Power November 1, 2018 @ 3:48 pm

    Which is better merge sort or heap sort?

    • May West November 14, 2018 @ 12:38 pm

      There are some differences between merge sort and heap sort. This will help you to decide which is a better sorting algorithm.

      • Merge sort uses divide and conquer technique to sort an array, while heap sort is a comparison based sorting algorithm.
      • Merge sort is stable while the heap sort is unstable because heap sort can change the relative order of equal items.
      • Merge sort works best on linked lists.
      • Heap sort needs less space than merge sort.
  9. Mohak Malhotra November 1, 2018 @ 3:49 pm

    Why is merge sort preferred for linked list?

    • Roxanne Sanders November 14, 2018 @ 12:59 pm

      Merge sort requires a small constant amount of auxiliary storage when merging that’s why it is preferred for a linked list. The slow random access of a linked list makes other algorithms like heapsort perform poorly. Unlike an array, in the linked list we can insert items in middle. Therefore merge operation of merge sort can be implemented simply without any extra space.

  10. Elena Lain November 1, 2018 @ 3:49 pm

    Which sort is the most efficient?

    • Yolanda Owens November 14, 2018 @ 1:32 pm

      The sorting technique with (n log n) complexity is best. Else the best sorting algorithm depends on the context.
      If you have a large input list for sorting, then merge sort, heap sort and quicksort will be the best algorithm. While for short input list, insertion sort performs best.
      You may decide the efficient sort as per your need.

  11. Imran Siddiqui November 1, 2018 @ 3:50 pm

    What is the time complexity of merge sort?

    • Mona Perry November 14, 2018 @ 1:33 pm

      The time complexity of two sorted arrays of length n, into another sorted array of length 2n, comes out to be O(2n). Merge sort is a recursive algorithm, so for n elements, you will have log (n) levels. Hence time complexity will be O(n log n) in all 3 cases (worst, average and best).

  12. Ashvinkumar Patel November 1, 2018 @ 3:51 pm

    Is merge sort recursive?

    • Richard Austin November 14, 2018 @ 1:34 pm

      Merge sort is a divide and conquer algorithm and it performs the same task on each level. Each time the function recurses so merge sort is known as a recursive algorithm.

  13. Andrew Hill November 1, 2018 @ 3:53 pm

    Which is the slowest sorting algorithm?

    • Tim Cain November 14, 2018 @ 1:35 pm

      If we compare the time complexity of merge sort, quicksort and heapsort then Heap sort is the slowest of O (n log n) sorting algorithm, but it does not require massive recursion or multiple steps to repeat like merge sort or quicksort. Else, the speed of any particular sorting algorithm depends on a few different factors.

  14. Janet Stocks November 1, 2018 @ 3:53 pm

    Is merge sort divide and conquer? Which sorting using divide and conquer strategy?

    • Trevor Clark November 15, 2018 @ 12:36 am

      Yes, merge sort is based on the technique of divide and conquer. There is one more sorting algorithm based on the divide and conquer technique i.e. Quicksort. Both algorithms based on the same technique. But the merge sort is more efficient and can be applied to any type of array.

  15. Jennifer Healy November 1, 2018 @ 3:54 pm

    What is an implementation of merge sort in Objective-C?

    • Darla Garcia November 15, 2018 @ 12:38 am

      Below is the example of merge sort in Objective-C: –
      – (NSArray *)arrayMergeSort:(NSArray *)targetArray
      {
      if (targetArray.count < 2)
      return targetArray;

      long midIndex = targetArray.count/2;

      NSArray *arrayLeft = [targetArray subarrayWithRange:NSMakeRange(0, midIndex)];

      NSArray *arrayRight= [targetArray subarrayWithRange:NSMakeRange(midIndex, targetArray.count – midIndex)];

      return [self arrayMerge: [self arrayMergeSort:arrayLeft] : [self arrayMergeSort:arrayRight]];
      }

  16. Johnathan Homer November 1, 2018 @ 4:00 pm

    What is the best case of merge sort?

    • Rafael Guerrero November 15, 2018 @ 12:39 am

      There are three cases which an algorithm expresses in terms of at least, at most and on average resource usage, which are best, worst and average cases.
      In merge sort, best case complexity is = O(n*log (n)). Although, complexity for all three cases is same in merge sort. Merge sort uses more space but it is stable.

  17. Peter Doherty November 1, 2018 @ 4:01 pm

    Which is faster merge sort or Quicksort?

    • Rex Mann November 15, 2018 @ 12:40 am

      Quicksort is faster than merge sort because in Quicksort there is no necessity to divide the list into a half, whereas in merge sort list is always divide into half. But at the same time, you can’t ignore the fact that Quicksort is not stable and merge sort is stable.

  18. Nigel Bright November 1, 2018 @ 4:02 pm

    Which is the fastest searching algorithm?

    • Lois Medina November 15, 2018 @ 12:41 am

      Usually, the sorting technique with O(n log n) complexity is fast. To choose the fastest searching algorithm depends on your need and size of the input list. If the list is not sorted then first you have to search for the element by linear search. Although, if you are searching for multiple times, it would be better if you sort (O(n log n)) then use binary search.

  19. Christine Forster November 1, 2018 @ 4:03 pm

    Which is the best algorithm for sorting?

    • Noel Beck November 15, 2018 @ 12:42 am

      The answer to this question is only “it depends on the input data and implementation”. If Merge sort is stable and efficient but needs larger space then others then Quicksort is faster than both but it is unstable. So each algorithm is ideal for a specific set of data you need to sort.

  20. Caspar Davies November 1, 2018 @ 4:03 pm

    What is the difference between sorting and searching?

    • Lamar Howard November 15, 2018 @ 12:43 am

      Sorting – This is the method used to arrange the terms or values in ascending or descending or alphabetical order or in a Data structure way. For example – you have 50 numbers and you want to arrange them in an ascending order.
      Searching – Search word implies to find a specific word or term in an array or group whether it is present or not. For example: – searching for a person from a group.

  21. Angela Landau November 1, 2018 @ 4:07 pm

    What type of algorithm is merge sort?

    • Ira Collins November 15, 2018 @ 12:45 am

      Merge sort is a kind of divide and conquer algorithm. It is the most popular and efficient algorithm. This is a great way to develop confidence in building a recursive algorithm. This repeats same steps in each level to sort an array or linked list. Merge sort preferred for the linked list.

  22. John Quirke November 1, 2018 @ 4:20 pm

    What are the real-time applications or real-life uses of merge sorting?

    • Sherri Hardy November 15, 2018 @ 12:47 am

      E-commerce application or website is the best real-time example of merge sort. They have a section “You might like ”, they have maintained an array of all users and according to that they start giving you recommendations.
      It is also used in tape drives to sort data. It’s good with parallel processing, which is why it is used there.

  23. MA November 19, 2018 @ 11:22 pm

    Could any one please explain the code which is in the main method?

    int main() {
    int a[100], aux[100], n, i, d, swap;

    printf(“Enter number of elements in the array:\n”);
    scanf(“%d”, &n);

    printf(“Enter %d integers\n”, n);

    for (i = 0; i < n; i++)
    scanf("%d", &a[i]);

    merge_sort(0, n – 1, a, aux);

    printf("Printing the sorted array:\n");

    for (i = 0; i < n; i++)
    printf("%d\n", a[i]);

    return 0;
    }

    • Hackr Team

      Hackr Team November 20, 2018 @ 12:46 pm

      Try to understand the Merge sort algorithm first using Pseudocode. Then understand the Merge sort code using the explanation given in the article. Once both these things are clear then understanding main() function is easier.

      The main() function first declares arrays and integers that are required in the function.
      Then it gives some output (using printf) to the user and gets some input (using scanf) from the user.
      Then it calls merge_sort() function which merge-sort the input array given to it and stores the output in the a[] array.
      Finally, the a[] array is printed.

      For more clarity, you can execute this Merge sort code in some online compiler like https://www.onlinegdb.com/online_c_compiler to better clarity.

Your email address will not be published. Required fields are marked *

*