Merge and Merge sort with example in C

Assume we have two ordered Integer arrays, a[] and b[]. If we wish to combine them into another ordered array, such as c[], we can use the following straightforward technique.

• Compare a[0] and b[0] first. Put whichever is smaller in c[0], say b[0].
• Compare and contrast a[0] with b[1]. Put whichever of the two is smaller, say b [1,] into c[1].
• Compare and contrast a [0] with b[2], put whichever is smaller, such as a [0], into c[2].
• Compare a [1] with b[2] and so on. One of the arrays a[] or b[] will eventually be exhausted.
• The remaining elements in the other array are simply copied into c[] at this point.

In file mergesort.h

#include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
void merge ( int a [ ], int b [ ], int c [ ], int m, int n ) ; 
void mergesort( int key [ ], int n )  ;
void wrt( int key [ ], int sz ) ;
in file merge.c
/ * merge a [ ] of size m\n and b [ ] of size n into c [ ] * /
# include “mergesort.h”
void merge ( int a [ ], int b [ ], int c [ ], int m, int n )
{
	int i = 0, j = 0, k = 0 ;
	while ( i< m && j < n )
		if ( a [ i ] < b [ j ] ) 
			c [ k  + + ] = a [ i + + ] ;
		else
			c [ k  + + ] = b [ j + + ] ;
	while ( i< m )
		c [ k  + + ] = a [ i + + ] ;
	while ( j< n )
		c [ k  + + ] = a [ j + + ] ;
}

It is expected that the array c [ ] has adequate area to accommodate both a [ ] and b[ ]. The programmer must ensure that the c[] boundaries are not exceeded. It's worth noting that one or both of the last two while statements, which are intended to gather up any remaining values, are not performed. This is due to the fact that at least one of the two criteria i< m and j< n will be false.

Next, we'll create a mergesort() method that calls merge(). A merge sort is far more efficient than a bubble sort. Our mergesort() function will operate on an array key[, which has a size of a power of two. The "power of two" condition will simplify the explanation. Let's pretend key [] has the following 16 numbers:

4

3

1

67

55

8

0

4

-5

37

7

4

2

9

1

-1

The data will be processed by the algorithm in several stages. The table below depicts how we want the data to be appeared after each pass:

Unordered data
4	3	1	67	55	8	0	4	-5	37	7	4	2	9	1	-1
First pass
3	4	1	67	8	55	0	4	-5	37	4	7	2	9	-1	1
Second pass
1	3	4	67	0	4	8	55	-5	4	7	37	-1	1	2	9
Third pass
0	1	3	4	4	8	55	67	-5	-1	1	2	4	7	9	37
Fourth pass
-5	-1	0	1	1	2	3	4	4	4	7	8	9	37	55	67

We want each succeeding pair of integers to be in order after the first pass. We want each succeeding quartet of integers to be in order after the second pass. We want each subsequent octet of Integers to be in order on the third pass. Finally, we want all 16 integers to be in order after the fourth run. Merge() is used at each stage to get the desired ordering. After the third iteration, for example, we have two sub-arrays.

0    1     3     4     4     8     55     67      and      -5     -1     1     2     4     7     9     37

Both of which are correct. We get the totally sorted array in the last line of the table by combining these two subarrays. Surprisingly, the code that does this is rather quick, demonstrating the power of pointer arithmetic.

In file mergesort.c
/ * mergesort : using merge ( ) for sorting an array if size n. * / 
#include "mergesort.h"
void mergesort (int keyl], int n)
{
Int J, K, m, * w ;
for ( m = 1 ; m < n ; m * =  2 ) 		/ * m is a power of 2 * /
if ( n< m ) {
print( " ERROR: Array size not a power of 2 – end !  \n " ) ;
exit ( 1 ) ;
	}
w= calloc( n, sizeof ( int ) ) ;			/ * allocate workspace * /
assert ( w 1 = NULL ) ;			/ * check that calloc ( ) worked * /
for ( k = 1 ; k < n ; K * = 2 ) {
for ( j = 0 ; j < n – K ; i + =  2 * k )
/ *
/ / Merge two subarrays of key [ ] into a subarray of w [ ].
* /
Merge ( key + j , key + j + k, W + J, k, k ) ;
for ( i = 0; j < n ; + + j )
key [ j ] = w [ j ] ;				/ * write w back into key * /
}
free(w);					/ *  free the workspace * /
}