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.
MERGE SORT

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 CaseO(n log n)
Best CaseO(n log n)
Average CaseO(n log n)
Space Complexity
Worst CaseO(n)

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 & space complexity and their applications. What is Quick Sort? Quick …
Read More

Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Bubble Sort? Bubble Sort …
Read More

Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C, time and space complexity and their advantages. What is Selection Sort? Selection …
Read More

Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C, time and space complexity and advantages.. What is Insertion sort? Insertion Sort …
Read More

Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Counting …
Read More

Radix Sort

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is …
Read More

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.

Leave a Comment

Your email address will not be published. Required fields are marked *