Hi, I've read article about merge sort from http://www.cprogramming.com/tutorial...ory/merge.html. I know there are a lot of code examples and a lot of explanation on how merge sort works, however often I found that code examples were not "very consistent", and it was usualy hard to follow. I went through code example of merge sort implementation and found that if condition
Code:
if(l < left + midpoint_distance &&
(r == right || max(input[l], input[r]) == input[l]))
is rather opaque, at least for me, while explantion of algorithm is excellent.
I'd like to suggest the following code.
Code:
static int merge_sort( int ar[], int len )
{
int* scratch = malloc( len * sizeof(int) );
if( scratch != NULL )
{
merge_helper( ar, 0, len - 1, scratch );
free( scratch );
return 1;
}
else
{
return 0;
}
}
static void merge_helper( int ar[], int left, int right, int scratch[] )
{
int middle = ( left + right ) / 2;
if ( right <= left )
{
return;
}
/* merge left subarray */
merge_helper( ar, left, middle, scratch );
/* merge right subarray */
merge_helper(ar, middle + 1, right, scratch );
/* merge arrays together using scratch for temp storage */
merge(ar, left, right, scratch);
}
static void merge( int ar[], int left, int right, int scratch[] )
{
int counter, i, j;
int middle = ( left + right ) / 2;
/* [1 9 | 6 7] --> [1 9 | 7 6] */
for (i = left, counter = 0; i <= middle; i++)
{
scratch[counter++] = ar[i];
}
for (j = right; j > middle; j-- )
{
scratch[counter++] = ar[j];
}
counter = left;
i = 0;
j = right - left;
/* [1 9 7 6]
* | |
* i j */
while ( i <= j )
{
if ( scratch[i] <= scratch[j] )
{
ar[counter++] = scratch[i++];
}
else
{
ar[counter++] = scratch[j--];
}
}
}
I'd like to add one more way to merge two sorted lists that is presented in this code:
Suppose we have two sorted lists that belong to one array:
[1 9 | 6 7]
first half is one list and second half is another list
This can be merge in the following way.
1. fill scratch array with first list and reverse second list.
In that case:
[1 9 | 7 6]
2. Initialize two search indexes i and j where i points to to the first element and j points to the last element
In this case:
i = 0 and j = 3
3. while ( i <= j) compare values scratch[i] and scratch[j] and smaller write to original array after which corresponding index is updated where i is incremented (if scratch [i] is written) or j is decremented (if scratch [j] is written to the array).
I think this implementation is easier to understand and faster than code example in the tutorial.
For example if original list was
[9 7 6 1],
then during of sorting process this list would look like:
[7 9 6 1]
[7 9 1 6]
[1 6 7 9]
I don't want to criticise or anything else, just want to present another code implementation that can be added to this great tutorial.
I'd like you to comment this and sorry because of bad English.
Maybe this post is for article discussion board, but I don't have privileges to post there
Thank you