Merge Sort one of the most famous sorting algorithm that uses divide and conquer technique.

Merge Sort divides the problem into sub problems and those sub problems are further divided into more sub problem and so on. Once the solution is ready, we combine the sub problems and get sorted list.

Basically merge sort has three steps:

Partition: Divide into two arrays L and R,elements in L are smaller than those in R.

Recursive: Sort K and R recursively.

Combine : Append R to the end of L.

The time complexity of merge sort is O(n logn).

Let’s understand the algorithm through pseudo code and see the steps.

Pseudo Code:

MERGE-SORT(A, p, r)
If p < r
q =  [ ( p + q ) /2 ]
MERGE-SORT(A, p, q)     //recursive function
MERGE-SORT(A, q+1, r)   //recursive function   
MERGE(A, p, q, r)       //calling Merge function
MERGE (A, p, q, r)

n1 = q – p +1
n2 = r – q
let L [1.. n1 + 1 ] and L [1.. n2 + 1 ]  be new arrays
for i=1 to  n1
L[ i ]  =  A [ p + i -1]
for j=1 to n2
R[ j ]= A[ q + j ]
L [n1 + 1 ] =  ∞
R [n2 + 1 ] =  ∞
i = 1
j = 1
for k = p to r
if L[ i ] < R [ j ]
A[ k ] = L[ i ]
i = i + 1
else  A[ k ] = R [ j ]
j = j + 1

Algorithm Steps :

Implementation:

C

# Merge sort in C
#include<stdio.h>

void Merge(int * , int , int , int );
void printArray(int [], int );
void MergeSort(int *array, int left, int right)
{
        int mid = (left+right)/2;
             if(left<right)
        {
             
                MergeSort(array,left,mid);
                
                MergeSort(array,mid+1,right);
                
                Merge(array,left,mid,right);
        }
}

void Merge(int *array, int start, int mid, int end)
{
        
        int tempArray[end-start+1];
        int pos=0,lpos = start,rpos = mid + 1;
        while(lpos <= mid && rpos <= end)
        {
                if(array[lpos] < array[rpos])
                {
                        tempArray[pos++] = array[lpos++];
                }
                else
                {
                        tempArray[pos++] = array[rpos++];
                }
        }
        while(lpos <= mid)  tempArray[pos++] = array[lpos++];
        while(rpos <= end)tempArray[pos++] = array[rpos++];
        int iter;
        
        for(iter = 0;iter < pos; iter++)
        {
                array[iter+start] = tempArray[iter];
        }
        return;
}
void printArray(int array[], int size)
{
  for (int i = 0; i < size; i++)
  {
    printf << array[i] << " ";
  }
  printf << endl;
}
int main()
{
int array[] = {2, 11, 5, 2};
  // Calculating size of a particular array.
  int size = sizeof(array) / sizeof(array[0]);
  merge_sort(array,1, size);
  printf << "Merge Sort:\n";
  printArray(array, size);
        return 0;
}


Java

import java.util.Arrays;
	
	 
	public class MergeSort {
	
	    public static void mergeSort(int[] array) {
	        mergeSort(array, 0, array.length-1);
	    }
	    private static void mergeSort(int[] array, int start, int end) {
	        if(start < end) {
	            int mid = (start+end)/2;
           mergeSort(array, start, mid);
	            mergeSort(array, mid+1, end);
	            merge(array, start, mid, end);
	        }
	    }
	
	    private static void merge(int[] array, int start, int mid, int end) {
	        int n1 = mid - start + 1;
	        int n2 = end - mid;
	        
        int[] temp1 = new int[n1];
	        int[] temp2 = new int[n2];
	        
	        for(int i = 0; i < n1; i++) {
	            temp1[i] = array[start+i];
	        }
	        
	        for(int j = 0; j < n2; j++) {
	            temp2[j] = array[mid+j+1];
	        }
	        
	        int i = 0, j = 0, k = start;
	        while(i < n1 && j < n2) {
	            if(temp1[i] <= temp2[j]) {
	                array[k] = temp1[i];
	                i++;
	            } else {
	                array[k] = temp2[j];
	                j++;
	            }
	            k++;
	        }
        
	        while(i < n1) {
	            array[k] = temp1[i];
	            i++;
	            k++;
	        }
	        while(j < n2) {
	            array[k] = temp2[j];
	            j++;
	            k++;
        }
	    }
	    
	    public static void main(String[] args) {
	        int[] array = {2,11,5,2};
	        mergeSort(array);
	        System.out.println("Merge Sort");
	        System.out.println(Arrays.toString(array));
	    }
	}

Python

def merge(input_array,first,middle,last):
    n1 = middle - first + 1
    n2 = last - middle

    L = [None for t in range(n1+1)]
    R = [None for t in range(n2+1)]

    
    for i in range(n1):
        L[i] = input_array[first + i - 1]
        
    for j in range(n2):
        R[j] =input_array[middle + j]
         

    L[n1] = SENTINEL
     
    R[n2] = SENTINEL
     

    i = 0
    j = 0 
    for k in range(first-1,last): 
        if L[i] <= R[j]:
            input_array[k] = L[i]
            i = i + 1
        else:
            input_array[k] = R[j]
            j = j + 1


def mergeSort(input_array,first,last):
    if first < last:
        middle =  int((first + last)/2) 
        mergeSort(input_array,first,middle)
        mergeSort(input_array,middle + 1,last)
        
        merge(input_array,first,middle,last)


arr = [5,2,4,7,1,3,2,6]
 
mergeSort(arr,1,len(arr))
print(arr)

C++

/* Merge sort in C++ */

#include<iostream>
using namespace std;

void merge_sort(int [],int ,int );
void merge(int [],int,int ,int );
void printArray(int [], int );

void merge_sort(int array[],int p,int r)
    {
        int q;
        if(p<r)
        {
         q=(p+r)/2;
         merge_sort(array,p,q);
         merge_sort(array,q+1,r);
         merge(array,p,q,r);
        }
    }

 void merge(int a[],int p,int q,int r)
    {
        
        int n1=q-p+1;
        int n2=r-q;
        int L[n1+1];
        int R[n2+1];
        for(int i=1;i<=n1;i++)
        {
            L[i]=a[p+i-1];
        }
        for(int j=1;j<=n2;j++)
        {
            R[j]=a[q+j];
        }
        L[n1+1]=999;
        R[n2+1]=999;
        int i=1, j=1;
        for(int k=p;k<=r;k++)
        {
            if(L[i]<=R[j])
            {
                a[k]=L[i];
                i=i+1;
            }
            else
            {
                a[k]=R[j];
                j=j+1;
            }
        }
    }

void printArray(int array[], int size)
{
  for (int i = 0; i < size; i++)
  {
    cout << array[i] << " ";
  }
  cout << endl;
}

int main()
{
	int array[] = {2, 11, 5, 2};
  // Calculating size of a particular array.
  int size = sizeof(array) / sizeof(array[0]);
  merge_sort(array,1, size);
  cout << "Merge Sort:\n";
  printArray(array, size);

}

Few Interview questions on Merge Sort:

Question– What is merge sort complexity for best case, average case and worst case?

Answer: O(n logn)

Question– You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

Answer: External Merge Sort


This can be done as follows:
1. Divide the data into 10 groups each of size 100 MB.
2. Sort each group in memory and write them to disk.
3. Load 10 items from each group into main memory.
4. Output the smallest item from the main memory to disk.
5. Load the next item from the group whose item was chosen.
6. Loop until all items are not outputted.
The step 3-6 is called as merging technique.

Short note about External Sorting:

External sorting is a term for a class of sorting algorithms that can handle massive amounts of data.
External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive).

That’s all I have and thanks a lot for reading. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance… 😉

Thanks a lot Abhijeet Gupta for helping us to grow. Abhijeet has good command in the data structure and he loves to solve the complex programming questions.


0 Comments

Leave a Reply

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

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert