C and Data Structures and Algorithms

Merge Sort in C – Algorithm and Program With Explanation

Posted in C, Data Structures and Algorithms
Merge Sort in C – Algorithm and Program With Explanation

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.

Aman Goel

Aman Goel

Entrepreneur, Coder, Speed-cuber, Blogger, fan of Air crash investigation! Aman Goel is a Computer Science Graduate from IIT Bombay. Fascinated by the world of technology he went on to build his own start-up - AllinCall Research and Solutions to build the next generation of Artificial Intelligence, Machine Learning and Natural Language Processing based solutions to power businesses. View all posts by the Author

Leave a comment

Your email will not be published
Cancel
GEDELA SANTOSH
GEDELA SANTOSH

Hi sir !
good morning aman goel sir!
i have nill knowledge in programming but i want to learn programming so plz give suggestion to how to learn programmings easily

N Alam
N Alam

Excellent

MA
MA

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 0 Points

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.

John Quirke
John Quirke

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

Sherri Hardy
Sherri Hardy

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.

Angela Landau
Angela Landau

What type of algorithm is merge sort?

Ira Collins
Ira Collins

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.

Caspar Davies
Caspar Davies

What is the difference between sorting and searching?

Lamar Howard
Lamar Howard

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.

Christine Forster
Christine Forster

Which is the best algorithm for sorting?

Noel Beck
Noel Beck

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.

Nigel Bright
Nigel Bright

Which is the fastest searching algorithm?

Lois Medina
Lois Medina

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.

Peter Doherty
Peter Doherty

Which is faster merge sort or Quicksort?

Rex Mann
Rex Mann

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.

Johnathan Homer
Johnathan Homer

What is the best case of merge sort?

Rafael Guerrero
Rafael Guerrero

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.