Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!samsung!olivea!mintaka!bloom-beacon!eru!hagbard!sunic!news.funet.fi!hydra!klaava!kruuna!wirzeniu
From: wirzeniu@kruuna.Helsinki.FI (Lars Wirzenius)
Newsgroups: comp.lang.c
Subject: Re: sorting doubly linked list
Summary: Try quicksort
Message-ID: <1991May14.112315.496@klaava.Helsinki.FI>
Date: 14 May 91 11:23:15 GMT
References: <OLSON.91May13142102@sol.aaet.csc.ti.com>
Sender: news@klaava.Helsinki.FI (Uutis Ankka)
Distribution: comp
Organization: University of Helsinki
Lines: 24

In article <OLSON.91May13142102@sol.aaet.csc.ti.com> olson@aaet.csc.ti.com (Doug Olson) writes:
>I need an efficient method of sorting these lists based on the key
>field. Any help would be greatly appreciated.

How about using a quicksort, ie. (in pseudocode):

	list quicsort(list) {
		if (list is not empty) {
			divide list into three sublists (less, equal,
				and greater than first element);
			quicksort(less);
			quicksort(greater);
			list = less + equal + greater;
			fix_the_other_links;
		}
		return list;
	}

While sorting, you should ignore the other link, and fix it afterwards
(left as an exercise :-).

I don't know if this is efficient enough, but it might very well be.
-- 
Lars Wirzenius  wirzenius@cc.helsinki.fi