# Merge Sort in C

Written by Shuvhojit DebFebruary 2, 2022
C
0 VIEWS 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 0 VIEWS SHARE
Shuvhojit Deb

Full Stack Developer

## Merge Sort Algorithm

Merge sort is a sorting method that uses the divide and conquers method. This essay will be highly useful and fascinating to students who may be asked about merge sort in their exams. Sorting algorithms are frequently asked in coding or technical interviews for software professionals. As a result, it is critical to debate the subject.

Merge sort is similar to the rapid sort algorithm in that it sorts the elements using a divide and conquer strategy. It's one of the most widely used and effective sorting algorithms. It splits the given list into two halves, then calls itself for each half and merges the two sorted parts. To perform the merging, we must define the merge() function.

## Syntax of Merge Sort in C

Merge sort in C does not have any particular syntax, but still, it follows some kind of steps and algorithm at the time of implementation, which is represented as follows:

The merge sort consists of some keys for the comparison of elements within the arrays:

1. Let the two divided arrays be arr [k….o] and arr [o+1…y] and let the merge key include (arr, o, k, y).

2. The key include (arr, o, k, y) is the merge key which is used for comparison and merging into two halves.

3. Now, some of the scenarios are followed to make the comparisons, including the entire key and the parameters defined so far.

4. If key > 1, then that algorithm will work in a way where the middle point will be searched for, and then the array will get divided into two halves after comparison with the key using the below formula.

Middle element_k = o+(y-k)/2

5. Call for the mergesort() function for the first half of the array from the bifurcated array.

Call merge_Sort (arr, k, o)

6. Call for the mergeSort() function for the next half of the array within the bifurcated array.

Call merge_Sort (arr, o, k, y)

## How does Merge Sort work in C?

As previously stated, the Merge sort is a sorting algorithm that uses the divide and conquers concept. So, let's take a look at the divide and conquer strategy. In the divide and conquer technique, the problem must be recursively divided into sub-problems, then dug and divided into the next set or subset of problems, and finally made final by backtracking and combining the subset with the solution one layer above or below. One thing to remember about the divide and conquer algorithm is that the division and sub-structure that follows the division should not cause the divided sub-problem to modify the original problem that was stated and delivered at the start.

The main emphasizing and important steps to be followed are the three steps starting from divide conquer and then combining it so that it has to be from bottom to top fashion for the final result. Merge sort has some advantages associated with it regarding efficiency, and it is very important to get the merge sort in C in terms of time complexity. Merge sort will comprise one entire array, containing all the elements and its associated key, value pairs into it for comparison and manipulation with other sets of elements in the array. The associated subset available with the merge function has to be proper for further division and combination into final results. Merge sort is one of the algorithms which include playing around with the elements and indexing.

Merge sort also adheres to the following time complexity, making the complete algorithm efficient and fast as required by the requirement and implementation:

• If we try to estimate the worst-case time complexity, then it will be O (n*logn)
• If we try to estimate the best case time complexity, then It will be O (n*logn)
• If we try to estimate the Average time complexity, then it will be O (n*logn)

Then merge sort algorithm can be applied to sort the elements, and in an entire program, only the merge sort function can be used for any other work.

## Implementation in C

We shall see the implementation of merge sort in C programming language here −

`#include <stdio.h>`
`#define max 10`
`int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };`
`int b[10];`
`void merging(int low, int mid, int high) {`
`   int l1, l2, i;`
`   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {`
`      if(a[l1] <= a[l2])`
`         b[i] = a[l1++];`
`      else`
`         b[i] = a[l2++];`
`   }`
`   `
`   while(l1 <= mid)    `
`      b[i++] = a[l1++];`
`   while(l2 <= high)   `
`      b[i++] = a[l2++];`
`   for(i = low; i <= high; i++)`
`      a[i] = b[i];`
`}`
`void sort(int low, int high) {`
`   int mid;`
`   `
`   if(low < high) {`
`      mid = (low + high) / 2;`
`      sort(low, mid);`
`      sort(mid+1, high);`
`      merging(low, mid, high);`
`   } else { `
`      return;`
`   }   `
`}`
`int main() { `
`   int i;`
`   printf("List before sorting\n");`
`   `
`   for(i = 0; i <= max; i++)`
`      printf("%d ", a[i]);`
`   sort(0, max);`
`   printf("\nList after sorting\n");`
`   `
`   for(i = 0; i <= max; i++)`
`      printf("%d ", a[i]);`
`}`

If we compile and run the above program, it will produce the following result −

#### Output:

`List before sorting`
`10 14 19 26 27 31 33 35 42 44 0`
`List after sorting`
`0 10 14 19 26 27 31 33 35 42 44`

## Conclusion

Merge sort is quite a useful algorithm in terms of efficiency as it follows the divide and conquer paradigm. This divide and conquer way is efficient because it helps in making the entire problem into sub-problems, making the computation and sorting process easy while keeping the original problem the same. Furthermore, it helps programmers to adopt this sorting because of its easy and simplified nature in terms of understanding.

C Language
Programming
C Algorithm
0 VIEWS 0 LIKES 0 DISLIKES SHARE
0 LIKES 0 DISLIKES 0 VIEWS SHARE
You must be Logged in to comment
Code Block
Shuvhojit Deb
Full Stack Developer
117 Blog Posts
Trending Technologies
15
Software91
DevOps48
Frontend Development24
Backend Development20
Data Center24
Sentry24
Terraform23
Ansible83
Docker70
Penetration Testing16
Kubernetes21
NGINX20
JenkinsX17

Techiio is on the journey to build an ocean of technical knowledge, scouring the emerging stars in process and proffering them to the corporate world.