Merge Sort

Mergesort is one of the older algorithms known since 1945. It is very good example of divide and conquer paradigm and is better than other simpler sort algorithms like selection, insertion or bubble sort.

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

So, merge sort algorithm is a recursive algorithm which calls itself on the smaller problem set.

So, we break the array into 2, then sort the 2 arrays, and re-merge them. Breaking the arrays until we reach the base case, so that we can come out or recursion :

Then we merge the 2 arrays, to get the array. Now we have 2 sorted arrays and we combine the arrays, and this is the step is called merge.

Merging the sorted array:

We will see how we can merge the 2 arrays in sorted order.

So, this is merge sort in picture:


Pseudocode for the merge sort algorithm
Here is the pseudocode for mergesort algorithm(recursive OR divide and conquer approach):

mergeSort(arr)
{
  list1 = arr(0-n/2);
  list2 = arr(n/2+1,n);
  list1 = mergeSort(list1);
  list2 = mergeSort(list2);
}

base case
0 or 1 element,

odd number case - In the pseudocode, I have skipped the complexity of array having odd number of elements.


Running time of the algorithm
Merging of 2 sorted array list1 and list2 of size m will be O(m), i.e. traversing 2 arrays of size m.

Also, we have to break the array into 2, until we reach the base case, where there were only 0 or 1 element left.
The height of this binary tree is log n. At each leven j, the size of the array is n/2j, as we have to pass half of the input size .

So, at level j, m = n/2j. So, merging 2 sorted arrays will take O(n/2j) which is O(n). So, total complexity is O(n log n).

Merging is the process of combining two or more sorted arrays into a third sorted array. We can use this technique to sort an array of n elements as follows.
Divide the array into ‘n’ sub arrays of size 1 and merge adjacent pairs of sub arrays. Then we can have approximately n/2 sorted sub arrays of size 2. Repeat this process until there is 1 array containing n elements.
Algorithm1. Establish a sub array ‘a’ with n elements
2. Let size < - 1 3. Repeat steps 4 through 6 until size >= n
4. Subdivide the sub array into sub arrays of size ‘size’
5. Merge adjacent pairs of sub arrays
6. Double the size

Here is the iterative implementation of mergesort in c:

#define MAX 20

void mergesort(int *,int);
void main()
{
 int x[MAX],n,j,i;
 char ans;
 clrscr();
 {
  printf("\nEnter The Length Of The Array\t: ");
  scanf("%d",&n);
  for(i=0;i< n;i++)
  {
   printf("Enter Element %d\t: ",i+1);
   scanf("%d",&x[i]);
  }
  mergesort(x,n);
  printf("\n\t│ Sorted Array :\t\t\t│\n\t│");
  for(i=0;i< n;i++)
   printf("%d\t",x[i]);
 }
 printf("│");
 getch();
}

void mergesort(int x[],int n)
{
 int sub[MAX];
 int i,j,k,list1,list2,u1,u2,size=1;
 while(size< n)
 {
  list1=0;
  k=0;

  while((list1+size)< n)
  {
   list2=list1+size;
   u1=list2-1;
   u2=((list2+size-1)< n)?(list2+size-1):(n-1);

   for(i=list1,j=list2;i< =u1 &&amp;amp; j< =u2;k++)
    if(x[i]< =x[j])
     sub[k]=x[i++];
    else
     sub[k]=x[j++];

   for(;i< =u1;k++)
    sub[k]=x[i++];

   for(;j< =u2;k++)
    sub[k]=x[j++];

   list1=u2+1;
  }
  for(i=list1;k< n;i++)
   sub[k++] = x[i];
  for(i=0;i< n;i++)
   x[i] =sub[i];
  size *= 2;
 }
}

Output:
/********* OUTPUT **********

Enter The Length Of The Array : 5
Enter Element 1 : 12
Enter Element 2 : 69
Enter Element 3 : 78
Enter Element 4 : 2
Enter Element 5 : 5

│ Sorted Array : │
│2 5 12 69 78 │