Merge Sort in C

How Merge Sort Works in C

Merge Sort is an example of the divide and conquer approach. It divides the array into equal halves and then combines in a sorted manner. In merge sort the unsorted list is divided into N sub-lists, each having one element.

Merge sort Divide and Conquer
Time Complexity Θ(n Log n)
Best Case Ω(n Log n)
Worst Case O(n Log n)
Space Complexity O(n)

Execution of Merge sort

Dividing

For an unsorted array and we will make a sorted array by using the merge sort algorithm in this array will be used divide and conquer technique.

First of all the array will be divided into N sub-arrays that is the array divided until each has only one element.

Conquering/Merging

The N sub-Arrays will then be merged one by one. Make sure that at each merging step the subarray becomes sorted (see image below). This part of the algorithm is called a conquering/merging.

The sub-arrays are merged in sorted fashion one by one till the resultant is the size of the actual array.

Merge Sort Working in C Intro

Program for Merge Sort

  • Method 1 – Two temporary subarrays
  • Method 2 – One Temporary subarray

Both will have the space complexity of O(N) as the combined size of two temporary arrays in method 1 will be the same as single temporary array used in method 2.

  • Space Complexity : O(n)
  • Time Complexity : O(n log n)
Run
#include <stdio.h>

void mergeSort(int[],int,int); 
void merge(int[],int,int,int);

void display(int arr[], int size){
    int i;
    for(i = 0; i < size; i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

void main() 
{
    int a[10]= {11, 9, 6, 19, 33, 64, 15, 75, 67, 88}; 
    int i; 

    int size = sizeof(a)/sizeof(a[0]);
    display(a, size);

    mergeSort(a, 0, size-1); 
    display(a, size);
}

void mergeSort(int a[], int left, int right)
{
    int mid;
    if(left < right)
    {
        // can also use mid = left + (right - left) / 2
        // this can avoid data type overflow
        mid = (left + right)/2;
        
        // recursive calls to sort first half and second half subarrays
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // create temp arrays to store left and right subarrays
    int L[n1], R[n2];
    
    // Copying data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
        
    // here we merge the temp arrays back into arr[l..r]
    i = 0; // Starting index of L[i]
    j = 0; // Starting index of R[i]
    k = left; // Starting index of merged subarray
    
    while (i < n1 && j < n2) 
    {
        // place the smaller item at arr[k] pos
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // Copy the remaining elements of L[], if any 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // Copy the remaining elements of R[], if any 
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

Output

11 9 6 19 33 64 15 75 67 88 
6 9 11 15 19 33 64 67 75 88
  • Space Complexity : O(n)
  • Time Complexity : O(n log n)
This method also has same space complexity as even though there are two temporary arrays created in previous approach. The combined size of still n in previous case and here also we have created even though one array but of size n.
Run
#include <stdio.h>

void mergeSort(int[],int,int); 
void merge(int[],int,int,int);

void display(int arr[], int size){
    int i;
    for(i = 0; i < size; i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

void main() 
{
    int a[10]= {11, 9, 6, 19, 33, 64, 15, 75, 67, 88}; 
    int i; 

    int size = sizeof(a)/sizeof(a[0]);
    display(a, size);

    mergeSort(a, 0, size-1); 
    display(a, size);
}

void mergeSort(int a[], int left, int right)
{
    int mid;
    if(left < right)
    {
        // can also use mid = left + (right - left) / 2
        // this can avoid data type overflow
        mid = (left + right)/2;
        
        // recursive calls to sort first half and second half subarrays
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

void merge(int a[], int left, int mid, int right)
{
    int i = left, j = mid + 1, p, index = left;
    int temp[10];

    while(i<=mid && j<=right)
    {
        if(a[i]<a[j]) { temp[index] = a[i]; i = i+1; } else { temp[index] = a[j]; j = j+1; } index++; } if(i>mid)
    {
        while(j<=right)
        {
            temp[index] = a[j];
            index++;
            j++;
        }
    }
    else
    {
        while(i<=mid)
        {
            temp[index] = a[i];
            index++;
            i++;
        }
    }
    p = left;
    while(p<index)
    {
        a[p]=temp[p];
        p++;
    }
}

Output

Input array - 11 9 6 19 33 64 15 75 67 88
Output array - 6 9 11 15 19 33 64 67 75 88
merge sort in C

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 100+ courses offered by PrepInsta in One Subscription

Quick Facts about Merge Sort

  • The complexity of the merge sort algorithm is O(NlogN) where N is the number of elements to sort.
  • It can be applied  to file of any sizes.
  • In Merge sort all the elements are divided into two sub-array again and again until one element is left.
  • After the completion of the divide and conquer the elements are merged to make a sorted array .
  • This sorting is less efficient and it require more space as compare to other sorting,

Merge Sort Advantages

  • Fast ! Time complexity : O(N Log N)
  • Reliable, it gives same time complexity in all cases.
  • Tim sort variant of this really powerful (Not important for Placements)

Merge Sort Disadvantages

  • Space Complexity sucks !!!
  • Space Complexity : O(n), most other algorithm have O(1)
Merge Sort in C meme

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 100+ courses offered by PrepInsta in One Subscription

Question 1.Prakash is using Merge sort to sort an array consisting of 2048 elements. After how many passes the array will be completely
sorted?

  1. 10
  2. 11
  3. 9
  4. 12

(Cisco, Goldman)

no. of stages = ciel(log2(2048)) = 11

The number of iterations to do so will always be ciel(log2(number of elements)) 

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting