How does Merge Sort Work? With complete solutions #9 by Md Farrukh Asif

 

MERGE SORT

How does Merge Sort Work?

Merging is combining two or more sorted arrays into a third sorted array. It was one of the first sorting algorithms used on a computer and was developed by John Von Neumann. Divide the array into approximately n/2 sub-arrays of size two and set the element in each sub array. Merging each sub-array with the adjacent sub-array will get another sorted sub-array of size four. Repeat this process until there is only one array remaining of size n.

Since at any time, the two arrays being merged are both sub-arrays of
A, lower, and upper bounds are required to indicate the sub-arrays of a being merged. l1 and u1 represent the lower and upper bands of the first sub-array and l2 and u2 represent the lower and upper bands of the second subarray respectively.

Let A be an array of n number of elements to be sorted
A[1], A[2] ...... A[n].

 Step 1: Divide the array A into approximately n/2 sorted sub-array of size 2. i.e., the elements in the (A [1], A [2]), (A [3], A [4]), (A [k], A [k + 1]),

(A [n – 1], A [n]) sub-arrays are in sorted order.

 

Step 2: Merge each pair of pairs to obtain the following list of sorted sub-array of size 4; the elements in the sub-array are also in the sorted order.

(A [1], A [2], A [3], A [4)),...... (A [k – 1], A [k], A [k + 1], A [k + 2]),

...... (A [n – 3], A [n – 2], A [n – 1], A [n].

 Step 3: Repeat the step 2 recursively until there is only one sorted

array of size n.

To illustrate the merge sort algorithm consider the following array with 7 elements [42], [33], [23], [74], [44], [67], [49]

ALGORITHM

Let A be a linear array of size n, A [1], A [2], A [3] ...... A [n], l1, and u1 represent the lower and upper bounds of the first sub-array, and l2 and u2 represent the lower and upper bound of the second sub-array. Aux is an auxiliary array of size n. Size is the size of merge files.

1.  Input an array of n elements to be sorted

2.  Size = 1

3.  Repeat through the step 13 while (Size < n) (a) set l1 = 0; k = 0

4.  Repeat through step 10 while ((l1+Size) < n) (a) l2 = l1+Size

(b) u1 = l2–1

5.  If ((l2+Size–1) < n)

(i) u2 = l2+Size–1

(b) Else

(i) u2 = n-1

6.  Initialize i = l1; j = l2 and repeat through step 7 if (i <= u1) and
( j < = u2)

7.  If (A [i] < = A[j])

(i) Aux [k] = A [i++]

(b) Else

(i) Aux [k] = A [j++]

8.  Repeat the step 8 by incrementing the value of k until (i < = u1) (a) Aux [k] = A [I++]

9.  Repeat the step 9 by incrementing the value of k until ( j < = u2) (a) Aux [k] = A [ j++]

10. L1=u2+1

11. Initialize I = l1 and repeat the step 11 if (k < n) by incrementing I by one (a) Aux [k++] = A[I]

12. Initialize I=0 and repeat the step 12 if (I < n) by incrementing I by one (a) A [i] = A [I]

13. Size = Size*2

14. Exit

===================

 PROGRAM USING ARRAYS (Copy and Run) 

//PROGRAM TO IMPLEMENT MERGING OF //TWO SORTED ARRAYS

//INTO A THIRD SORTED ARRAY

//CODED AND COMPILED IN TURBO C

#include<conio.h>

#include<stdio.h>

void main()

{

int arr1[20],arr2[20],arr3[40];

int i,j,k;

int max1,max2;

clrscr();

printf (“\nEnter the number of elements in list1 : ”);

scanf (“%d”,&max1);

printf (“\nTake the elements in sorted order :\n”);

for (i=0;i<max1;i++)

{

printf (“\nEnter element %d : ”,i+1);

scanf (“%d”,&arr1[i]);

}

printf (“\nEnter the number of elements in list2 : ”);

scanf (“%d”,&max2);

printf (“\nTake the elements in sorted order :\n”);

for (i=0;i<max2;i++)

{

printf (“\nEnter 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++];

}/*End of while*/

/*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++];

/*Merging completed*/

printf (“\nList 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]);

getch();

}/*End of main()*/

=======================

 PROGRAM WITHOUT RECURSION(Copy and Run)

//PROGRAM TO IMPLEMENT

//MERGE SORT WITHOUT RECURSION

//CODED AND COMPILED IN TURBO C

#include<stdio.h>

#include<conio.h>

#define MAX 30

void main()

{

int arr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”,&n);

for (i=0;i<n;i++)

{

printf (“\nEnter element %d : ”,i+1);

scanf (“%d”,&arr[i]);

}

printf (“\nUnsorted list is : ”);

for ( i = 0 ; i<n ; i++)

printf(“%d ”, arr[i]);

/*l1 lower bound of first pair and so on*/

for (size=1; size < n; size=size*2 )

{

l1 = 0;

k = 0; /*Index for temp array*/

while( l1+size < n)

{

h1=l1+size–1;

l2=h1+1;

h2=l2+size–1;

if ( h2>=n ) /* h2 exceeds the limlt of arr */

h2=n-1;

/*Merge the two pairs with lower limits l1 and l2*/

i=l1;

j=l2;

while(i<=h1 && j<=h2 )

{

if ( arr[i] <= arr[ j] )

temp[k++]=arr[i++];

Else

temp[k++]=arr[ j++];

}

while(i<=h1)

temp[k++]=arr[i++];

while( j<=h2)

temp[k++]=arr[ j++];

/**Merging completed**/

l1 = h2+1; /*Take the next two pairs for merging */

}/*End of while*/

for (i=l1; k<n; i++) /*any pair left */

temp[k++]=arr[i];

for(i=0;i<n;i++)

arr[i]=temp[i];

printf (“\nSize=%d \nElements are : ”,size);

for ( i = 0 ; i<n ; i++)

printf (“%d ”, arr[i]);

}/*End of for loop */

printf (“\nSorted list is :\n”);

for ( i = 0 ; i<n ; i++)

printf (“%d ”, arr[i]);

getch();

}/*End of main()*/

========================

 PROGRAM THROUGH RECURSION (Copy and Run) 

//PROGRAM TO IMPLEMENT

//MERGE SORT THROUGH RECURSION //CODED AND COMPILED IN TURBO C

#include<stdio.h>

#include<conio.h>

#define MAX 20

int array[MAX];

//Function to merge the sub  files or arrays

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++] ;

}/*End of while*/

while( i <= mid )

temp[k++]=array[i++];

while( j <= high )

temp[k++]=array[j++];

for (i= low; i < = high ; i++)

array[i]=temp[i];

}/*End of merge()*/

//Function which call itself to sort an array

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 );

}

}/*End of merge_sort*/

void main()

{

int i,n;

clrscr();

printf (“\nEnter the number of elements : ”);

scanf (“%d”,&n);

for (i=0;i<n;i++)

{

printf (“\nEnter element %d : ”,i+1);

scanf (“%d”,&array[i]);

}

printf (“\nUnsorted 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]);

getch();

}/*End of main()*/

=========================

 TIME COMPLEXITY

Let f (n) denote the number of comparisons needed to sort an n element array A using the merge sort algorithm. The algorithm requires almost log n passes, each involving n or fewer comparisons.

 

In average and worst case the merge sort requires O(n log n ) comparisons.

The main drawback of merge sort is that it requires O(n) additional space for the auxiliary array.

 ===========================

Share, Like and Comment Please……

===========================