# Merge Sort

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:

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

### Implementation of Merge Sort

#### Program Code in C :-

```.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
```#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);

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)`

### Applications of Merge Sort

1. Inversion count problem
2. External sorting
3. E-commerce applications

### Other Sorting Algorithms :-

#### Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time…

#### Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time…

#### Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C,…

#### Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C,…

#### Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C,…