Merge Sort

November 10, 2009

The last O(n log n) sorting algorithm that we shall consider in our current series of exercises is merge sort. If you have two sorted sequences, they can be merged into a single sorted sequence in time linear to their combined length by running through them in order, at each step taking the smaller of the heads of the two sequences. Then mergesort works by recursively merging smaller sequences into larger ones, starting with trivially-sorted sequences of one element that are merged into two-element sequences, then merging pairs of two-element sequences into four-element sequences, and so on, until the entire sequence is sorted.

Your task is to write a function that sorts an array by the merge sort algorithm described above, according to the conventions of the prior exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

2 Responses to “Merge Sort”

  1. r. clayton said

    An idiotically cumbersome Java mergesort implementation. The private mergesort returns a pointer to the fully sorted (unsegmented) array.

  2. Vikas Tandi said

    My implementation in C

    #define MODCOPY(x,y) (((x) < 0) ? ((x) = (-y)) : ((x) = (y)))
    
    typedef struct ElementNode
    {
    	int key;
    	int link;
    }element;
    
    static void mergesort_imp(element arr[], int left, int right);
    static void swap(element arr[], int i, int j);
    
    void mergesort(element arr[], int left, int right)
    {
    	int p, q, k;
    	/* arrange the links in sorted order */
    	mergesort_imp(arr, left, right);
    
    	/* sort the records in-place according to the links */
    	p = left-1;
    	k = left;
    	while(arr[p].link)
    	{
    		if(p < k)
    		{
    			p = arr[p].link;
    			continue;
    		}
    		swap(arr, k, p);
    		q = arr[k].link;
    		arr[k].link = p;
    		p = q;
    		k++;
    	}
    }
    
    /* arr[left-1] and arr[right+1] are two artificial nodes at the start and the end of list.
    	A negative link denotes the end of a sublist known to be ordered; a zero link indicates
    	the end of the entire list */
    static void mergesort_imp(element arr[], int left, int right)
    {
    	int i;
    	int s, t , p, q;
    
    	/* prepare two lists */
    	arr[left-1].link = left;
    	arr[right+1].link = left+1;
    
    	/* initially the file is assumed to be unordered,
    		so setting all links to negative value */
    	for(i = left; i < (right-1); i++)
    		arr[i].link = -(i+2);
    
    	arr[right-1].link = 0;
    	arr[right].link = 0;
    
    	/* we have created two lists out of which one list contain all odd positioned elements
    		and other list contain all even positioned elements */
    
    	/* main loop */
    	for(;;)
    	{
    		/* begin new pass */
    		s = left-1;
    		t = right+1;
    		p = arr[s].link;
    		q = arr[right+1].link;
    
    		if(q == 0)			/* terminate */
    			break;
    
    		for(;;)
    		{
    			/* compare keys */
    			if(arr[p].key > arr[q].key)
    			{
    				MODCOPY(arr[s].link, q);
    				s = q;
    				q = arr[q].link;
    
    				if(q <= 0)
    				{
    					arr[s].link = p;
    					s = t;
    					do
    					{
    						t = p;
    						p = arr[p].link;
    					}
    					while(p > 0);
    
    					p = -p;
    					q = -q;
    				}
    			}
    			else
    			{
    				MODCOPY(arr[s].link, p);
    				s = p;
    				p = arr[p].link;
    
    				if(p <= 0)
    				{
    					arr[s].link = q;
    					s = t;
    					do
    					{
    						t = q;
    						q = arr[q].link;
    					}
    					while(q > 0);
    
    					p = -p;
    					q = -q;
    				}
    			}
    
    			if(q == 0)
    				break;
    		}
    		MODCOPY(arr[s].link, p);
    		MODCOPY(arr[t].link, 0);
    	}
    }
    
    static void swap(element arr[], int i, int j)
    {
    	element temp;
    
    	temp.key = arr[i].key;
    	temp.link = arr[i].link;
    
    	arr[i].key = arr[j].key;
    	arr[i].link = arr[j].link;
    
    	arr[j].key = temp.key;
    	arr[j].link = temp.link;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 612 other followers

%d bloggers like this: