Merge sort

      No Comments on Merge sort

Like Quick Sort Merge sort is also application of Divide and Conquer design technique. This algorithm divides the input array into two halves, and recursively calls itself for the halves. Then it merges the sorted array using the Merge algorithm.

Merge Sort

  • It is an out-place sorting technique.This means merge sort using extra space to sort the input array.
  • It is a stable sorting algorithm.
  • Merge sort uses Merge algorithm to merge two sorted arrays which has time complexity of
    O(n).

The following diagram from wikipedia shows the complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. We can clearly notice that the array is recursively divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.
Merge sort

Merge Algorithm:

Algorithm:

Merge(a,start,mid,end)
  1. Create two temporary arrays for two halves.
  2. Copy elements for temporary array to output array in sorted order
      if(left[i]<=right[j]) 
         Set array[k]=left[i]
      else
         Set array[k]=right[j]
  3. Copy rest elements  

Time complexity:
Time complexity of merge algorithm depends on two things:

  1. Comparisons
  2. Moves (copying elements to new array)

In each case, number of moves required will be the same. If one array has ‘m‘ elements and other has ‘n‘ elements, then moves required will be m+n.

In best case, number of comparisons will equal to the number of elements in smaller array, i.e minimum(m,n).Therefore,

 Time complexity in best case T(n) for input size n;
  T(n) = comparisons + moves  
       = minimum(m,n) + m+n
       = O(m+n)
       = O(n) // when number of elements in both arrays are same

In worst case, number of comparisons will equal to m+n-1. Therefore,

Time complexity in worst case T(n) for input size n;
 T(n) = comparisons + moves
      = m+n-1 + m+n
      = O(m+n)

Merge Sort

Algorithm:

MergeSort(a,i,j)
  if(j>i)
  1. Find middle to divide the arrays into two halves.
     mid=  (i+j)/2 ----> O(1)
  2. Call merge sort algorithm for first half
     MergeSort(a,i,mid)  ------> T(n/2)
  3. Call merge sort for the second half
     MergeSort(a,mid+1,j) ------>T(n/2)
  4. Call merging algorithm for the two sorted arrays.
     Merge(a,i,mid,j)  -----> O(n)

Time complexity:

 Time complexity T(n) for input size of n;
  T(n) = T(n/2)+ T(n/2) + n + c
       = 2T(n/2) + n + c
       solving recurrence relation,
       = 2^2T(n/2^2) + n + n
       =2^3T(n/2^3) + n + n + n
       |
       |  k times
       |
       = 2^kT(n/2^k) + n + n + n....k times
       letting n/2^k =1 
       taking  log on both sides we get
       log n = k
       = 2^k T(1) + kn
       = n (leaf level cost)  + nlogn  (intermediate level cost) 
       = O(nlogn)

Note: Merge sort has same complexity in best , average or worst case as merge sort always divides the array in two halves and take linear time to merge two halves.
Space complexity:
Space complexity takes in count the space taken by input and extra auxiliary space.

  S(n) = i/p + extra space
       = (size of data type)*n (for input array of n size )  
         + (size of data type) *n ( for extra array) 
         + logn ( stack for recursive calls, as we will have a tree with logn levels)
       = O(n)

Implementing Merge sort in c

#include<stdio.h>
void merge(int arr[], int start, int mid, int end)
{
    int i, j, k;
    
    /* Calculate the size of 2 sub arrays */
    int n1 = mid -start + 1;
    int n2 =  end - mid;
 
    /* create temp arrays */
    int Left[n1], Right[n2];
 
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        Left[i] = arr[start + i];
    for (j = 0; j < n2; j++)
        Right[j] = arr[mid + 1+ j];
 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = start; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (Left[i] <= Right[j])
        {
            arr[k] = Left[i];
            i++;
        }
        else
        {
            arr[k] = Right[j];
            j++;
        }
        k++;
    }
 
    /* Copy the remaining elements of L[], if there
       are any */
    while (i < n1)
    {
        arr[k] = Left[i];
        i++;
        k++;
    }
 
    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        arr[k] = Right[j];
        j++;
        k++;
    }
}
void mergesort(int arr[],int start, int end)
{
	if(end>start)
	{
		/*Calculate middle */
		int mid=(start+end)/2;
		
		/* Call mergesort for two halves */
		mergesort(arr,start,mid);
		mergesort(arr,mid+1,end);
		
		/* Call merge algo*/
		merge(arr,start,mid,end);
	}
}
/* utility function to print array */
void printarray(int a[],int n)
{
	int k=0;
	for(;k<n;k++)
	printf("%d\t",a[k]);
}
int main()
{
	int arr[]={4,6,70,88,3,5,7,10};
	int n=sizeof(arr)/sizeof(arr[0]);
	
	/* initial array */ 
	printf("Given array:\n");
	printarray(arr,n);
	
	/* call merge sort */
	mergesort(arr,0,n-1);
	
	/*sorted array */
	printf("\nSorted array:\n");
	printarray(arr,n);
	return 0;
}

Summary
Merge sort
Article Name
Merge sort
Description
Merge sort is application of Divide & Conquer technique. This algorithm divides the input array into two halves, and recursively calls itself for the halves
Author
Publisher Name
Scanfcode
Publisher Logo

Leave a Reply

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