sorting doubly linked list

[Lars Wirzenius]

In article <OLSON.91May13142102 at sol.aaet.csc.ti.com> olson at 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 at cc.helsinki.fi