Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications.

**What is Merge Sort?**

**Merge Sort** is a *divide and conquer algorithms* based on the idea of breaking down a list into several sub-lists.

The algorithm starts breaking down a list into sub-lists and apply sorting algorithms then merge two sorted sub-lists into lager sorted list.

Merge Sort accesses the data in a sequential manner.

Merge sort is Quick Sort’s complement.

This algorithm is used for *sorting a linked list.*

Merge Sort is not an in place sorting algorithm because in the merge sort algorithm it is taking O(n) extra space.

**Algorithm**

Merge sort operates as follow:

- Divide the n-element list into two sub-lists.
- Sort the two sub-lists recursively using merge sort.
- Merge the two sorted sub-lists to produce the sorted list.

**Implementation of Merge Sort**

**Program Code in C :-**

```
#include<stdio.h>
//Merge two sub-arrays L and M into arr
void merge(int arr[], int p, int q, int r)
{
//Create L and M sub-arrays
int n1 = q-p+1;
int n2 = r-q;
int L[n1], M[n2];
for(int i=0; i<n1; i++)
L[i] = arr[p+i];
for(int j=0; j<n2; j++)
M[j] = arr[q+1+j];
//Maintain current index of sub-arrays and main memory
int i, j, k;
i=0;
j=0;
k=p;
while(i<n1 && j<n2)
{
if(L[i] <= M[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = M[j];
j++;
}
k++;
}
while(i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while(j < n2)
{
arr[k] = M[j];
j++;
k++;
}
}
//Divide array into two subarrays, sort them and merge them.
void mergesort(int arr[], int l, int r)
{
if(l < r)
{
int m = l+(r-l)/2;
mergesort(arr, l, m);
mergesort(arr, m+1, r);
//Merge the sorted subarrays
merge(arr, l, m, r);
}
}
//print array
void printarray(int arr[], int size)
{
for(int i=0; i<size; i++)
printf("%d ",arr[i]);
printf("\n");
}
//Driver program
int main()
{
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int size = sizeof(arr)/sizeof(arr[0]);
mergesort(arr, 0, size-1);
printf("Sorted array : ");
printarray(arr, size);
}
```

Code language: C++ (cpp)

**Output** **:-**

`Sorted array : 3 9 10 27 38 43 82`

Code language: PHP (php)

**Time and Space Complexity of Merge Sort**

Time Complexity | |

Worst Case | O(n log n) |

Best Case | O(n log n) |

Average Case | O(n log n) |

Space Complexity | |

Worst Case | O(n) |

**Applications of Merge Sort**

- Inversion count problem
- External sorting
- E-commerce applications

### Other Sorting Algorithms :-

- Bubble Sort
- Insertion Sort
- Selection Sort
- Counting Sort
- Bucket Sort
- Radix Sort
- Quick Sort
- Heap Sort
- Shell Sort

### Related:

*Want to Contribute*:-

If you like “**To The Innovation**” and want to contribute, you can mail your articles to **[email protected]**. See your articles on the main page and help other coders.