# 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 :-

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

### Applications of Merge Sort

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

### Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to ðŸ“§ contribute@totheinnovation.com. See your articles on the main page and help other coders.ðŸ˜Ž

Scroll to Top