Merge Sort

Last updated on September 4th, 2023 at 09:46 pm

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 82Code language: PHP (php)

Time and Space Complexity of Merge Sort

Applications of Merge Sort

1. Inversion count problem
2. External sorting
3. 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.😎