2-way merge sort

Merge sort is a sorting technique which is generally applied between two sorted arrays. Here a third array is created and the elements of both the sorted arrays are matched, correspondingly, the third array is filled. Hence, the final third array obtained will be consisting of elements belonging to both the arrays in sorted order.

Merge Sort Algorithm

Merge sort time complexity

merge sort implementation

#include<stdio.h>

int main()
{
  int arr1[20],arr2[20],arr3[40];
  int i,j,k;
  int max1,max2;
  printf("Enter the number of elements in list1 : ");
  scanf("%d",&max1);
  printf("Take the elements in sorted order :\n");
  for(i=0;i<max1;i++)
  {
    printf("Enter element %d : ",i+1);
    scanf("%d",&arr1[i]);
  }
  printf("Enter the number of elements in list2 : ");
  scanf("%d",&max2);
  printf("Take the elements in sorted order :\n");
  for(i=0;i<max2;i++)
  {
    printf("Enter element %d : ",i+1);
    scanf("%d",&arr2[i]);
  }
  /* Merging */
  i=0;  	/*Index for first array*/
  j=0;  	/*Index for second array*/
  k=0;  	/*Index for merged array*/

  while( (i < max1) && (j < max2) )
  {
    if( arr1[i] < arr2[j] )
      arr3[k++]=arr1[i++];
    else
      arr3[k++]=arr2[j++];
  }
  /*Put remaining elements of arr1 into arr3*/
  while( i < max1 )
    arr3[k++]=arr1[i++];
  /*Put remaining elements of arr2 into arr3*/
  while( j < max2 )
    arr3[k++]=arr2[j++];

  
  printf("List 1 :  ");
  for(i=0;i<max1;i++)
    printf("%d ",arr1[i]);
  printf("\nList 2 :  ");
  for(i=0;i<max2;i++)
    printf("%d ",arr2[i]);
  printf("\nMerged list : ");
  for(i=0;i<max1+max2;i++)
    printf("%d ",arr3[i]);
  printf("\n");
        return 0;
}

Analysis

Let us take an array of size n is used for merge sort. Because here we take elements in pair and merge with another pair after sorting. So merge sort requires maximum log2n passes. Each pass, total number of comparison can be maximum n. hence we can say merge sort requires maximum n* log2 n compares with is of O(nlog2n). The main disadvantage of merge sort is space requirement it requires extra space of O(n).

merge sort implementation using recursion

/* Program of sorting using merge sort through recursion*/
#include<stdio.h>
#define MAX 20
int array[MAX];

void merge( int low, int mid, int high )
{
  int temp[MAX];
  int i = low;
  int j = mid +1 ;
  int k = low ;

  while( (i <= mid) && (j <=high) )
  {
    if(array[i] <= array[j])
      temp[k++] = array[i++] ;
    else
      temp[k++] = array[j++] ;
  }

  while( i <= mid )
    temp[k++]=array[i++];
  while( j <= high )
    temp[k++]=array[j++];

  for(i= low; i <= high ; i++)
    array[i]=temp[i];
}

void merge_sort( int low, int high )
{
  int mid;
  if( low != high )
  {
    mid = (low+high)/2;
    merge_sort( low , mid );
    merge_sort( mid+1, high );
    merge( low, mid, high );
  }
}

int main()
{
  int i,n;
  printf("Enter the number of elements : ");
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    printf("Enter element %d : ",i+1);
    scanf("%d",&array[i]);
  }

  printf("Unsorted list is :\n");
  for( i = 0 ; i<n ; i++)
    printf("%d ", array[i]);

  merge_sort( 0, n-1);

  printf("\nSorted list is :\n");
  for( i = 0 ; i<n ; i++)
    printf("%d ", array[i]);
  printf("\n");
        return 0;
}