Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!mit-eddie!uw-beaver!cornell!hilfingr
From: hilfingr@rama.cs.cornell.edu (Paul N. Hilfinger)
Newsgroups: comp.lang.c
Subject: Re: Sorting Double Linked List in place
Message-ID: <48172@cornell.UUCP>
Date: 10 Nov 90 07:33:30 GMT
References: <1990Nov7.160701.5838@bkj386.uucp> <14403@smoke.brl.mil> <658158129@juliet.cs.duke.edu>
Sender: nobody@cornell.UUCP
Reply-To: hilfingr@cs.cornell.edu (Paul N. Hilfinger)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 109

I found that the following code (which uses O(lg(N)) extra space, but
so what) works pretty well.  On my DECSTATION 3100 using gcc -O, it
runs about 2.5 times faster than another posted mergesort on one set
of 24000 integers, but what's a constant factor among colleagues?

The algorithm uses a binomial comb to collect merged sublists.

Paul Hilfinger

------------------------cut here----------------------------------------------

#include <stdlib.h>
#include <stdio.h>

/*
** An entry in a doubly linked list (from D. Richard Hipp)
*/
typedef struct s_dbllink {
  int key;
  struct s_dbllink *prev, *next;
} dblink;

#define NEXT(L) ((L) -> next)
#define PREV(L) ((L) -> prev)
#define KEY(L)  ((L) -> key)


#define LG_MAX_LIST 48

static dblink *merge(dblink *L0, dblink *L1);

void dblSort1(dblink **LP)
    /* Assumptions:							*/
    /*     The list *LP has no more than 2**LG_MAX_LIST elements.	*/
    /* Effect:								*/
    /*     Destructively sorts the list pointed to by *LP in		*/
    /*     increasing lexicographic order by key, setting *LP to point 	*/
    /*     to the head of the resulting list.  			        */
{
    dblink *BIN[LG_MAX_LIST]; /* List headers */
    dblink *L;
    int i;

    for (i = 0; i < LG_MAX_LIST; i += 1)
	BIN[i] = NULL;

    L = *LP;
    while (L != NULL) {
	dblink *M = L;

	L = NEXT(L);
	NEXT(M) = NULL;
	
	for (i = 0; BIN[i] != NULL; i += 1) {
	    M = merge(BIN[i], M);
	    BIN[i] = NULL;
	}
	BIN[i] = M;
    }

    for (L = BIN[0], i = 1; i < LG_MAX_LIST; i += 1)
	L = merge(BIN[i], L);

	/* Re-establish back links. */
    if (L != NULL) {
	dblink *P;

	L -> prev = NULL;
	for (P = L; NEXT(P) != NULL; P = NEXT(P))
	    PREV(NEXT(P)) = P;
    }

    *LP = L;
}

static dblink *merge(dblink *L0, dblink *L1)
    /* Assumptions:							*/
    /*     L0, L1 are sorted in increasing order by key.		*/
    /* Effects:								*/
    /*     Destructively merges L0 and L1 into increasing order.	*/
    /*     Equal elements in L0 are placed before ones in L1.		*/
    /*     Returns a pointer to the header of the list.			*/
    /*     PREV values are unreferenced (and hence, invalid).           */
{
    dblink **last;
    dblink *head;

    last = &head;

    while (L0 != NULL && L1 != NULL) {
	if (KEY(L0) <= KEY(L1)) {
	    *last = L0;
	    L0 = NEXT(L0);
	}
	else {
	    *last = L1;
	    L1 = NEXT(L1);
	}

	last = &NEXT(*last);
    }

    if (L0 == NULL)
	*last = L1;
    else
	*last = L0;

    return head;
}