Merge Sort - Algorithm - TO THE INNOVATION

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 82Code 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 :-

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.😎