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 📧 contribute@totheinnovation.com. See your articles on the main page and help other coders.😎