Merge Sort

November 10, 2009

It is awkward to sort arrays by merge sort, since it requires two arrays, an input array and an output array; merge sort is used far more often to sort linked lists, as in the Standard Prelude. We begin with a function that merges two sub-arrays, left through middle and middle + 1 through right, from an input array into the positions left through right in an output array:

function merge(A,left,middle,right,    B,i,j,k) {
    i = left; j = middle + 1
    while (i <= middle && j <= right)
        if (A[i] <= A[j]) B[++k] = A[i++]
        else B[++k] = A[j++]
    while (i <= middle)
        B[++k] = A[i++]
    while (j <= right)
        B[++k] = A[j++]
    for (k = left; k <= right; k++) {
        A[k] = B[k]; delete B[k] } }

Here i indexes the first sub-array, j indexes the second sub-array, and k indexes the output array; we take advantage of Awk’s implicit initialization for k = 0. The first while loop runs until one of the sequences ends, the second and third while loops pick up the remainders of the runs, and the fourth while loop copies the output array back to the input array. Notice that we broke our convention, using less-than-or-equal instead of less-than to compare array elements; doing so allows our sort to be stable, with equal elements appearing in the output in the same order as the input.

Given merge, the actual sort function splits the array in two, sorts the two halves recursively, then merges them together:

function mergesort(A,left,right,    middle) {
    if (left < right) {
        middle = int((left + right) / 2)
        mergesort(A, left, middle)
        mergesort(A, middle + 1, right)
        merge(A, left, middle, right) } }

function sort(A,n) { mergesort(A, 1, n) }

If you like, you can move the merge inline and eliminate recursion; l1 and l2 index the lower bounds of the two sub-arrays, u1 and u2 index the upper bounds of the two sub-arrays, k indexes the output array, and g is the gap between the two sub-arrays, which doubles at each pass:

function sort(A,n,    l1,l2,u1,u2,k,g,B) {
    for (g = 1; g < n; g *= 2) {
        k = 0
        for (l1 = 1; l1 + g <= n; l1 = u2 + 1) {
            l2 = l1 + g; u1 = l2 - 1
            u2 = l2 + g - 1; if (u2 > n) u2 = n
            while (l1 <= u1 && l2 <= u2)
                if (A[l1] <= A[l2])
                    B[++k] = A[l1++]
                else B[++k] = A[l2++]
            while (l1 <= u1)
                B[++k] = A[l1++]
            while (l2 <= u2)
                B[++k] = A[l2++] }
        while (k < n)
            B[++k] = A[l1++]
        for (k = 1; k <= n; k++)
            A[k] = B[k] } }

All of the code, including the test suite of the prior exercise, is collected at http://programmingpraxis.codepad.org/Wk6rsu1Z, but you can't run it because codepad doesn't provide an Awk interpreter.

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 630 other followers