Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!rphroy!caen!uwm.edu!psuvax1!rutgers!cmcl2!adm!smoke!gwyn
From: gwyn@smoke.brl.mil (Doug Gwyn)
Newsgroups: comp.lang.c
Subject: Re: sorting doubly linked list
Message-ID: <16150@smoke.brl.mil>
Date: 14 May 91 19:32:42 GMT
References: <OLSON.91May13142102@sol.aaet.csc.ti.com>
Organization: U.S. Army Ballistic Research Laboratory, APG, MD.
Lines: 8

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.

Convert the doubly-linked list to a binary search tree (you already
have the link fields needed for that), then (if there is any need to
do so) traverse the tree in inorder, moving the nodes as they are
processed onto the tail of a doubly-linked list.