Thread: merge sort tutorial from cprogramming.com

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715

    merge sort tutorial from cprogramming.com

    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
    Last edited by Micko; 03-15-2005 at 09:57 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. plzzzzzz... i need a help in natural merge sort
    By sam-j89 in forum C++ Programming
    Replies: 23
    Last Post: 05-11-2009, 01:43 PM
  2. Merge Sort - Invalid Output ??
    By gqchynaboy in forum C++ Programming
    Replies: 3
    Last Post: 09-25-2005, 05:01 PM
  3. sort algorithm (merge?)
    By mouse163 in forum C++ Programming
    Replies: 1
    Last Post: 04-07-2003, 08:05 AM
  4. Merge Sort using a linked list
    By EvenFlow in forum C Programming
    Replies: 0
    Last Post: 10-04-2001, 11:07 PM
  5. merge sort
    By Unregistered in forum C Programming
    Replies: 0
    Last Post: 09-02-2001, 06:58 PM