sorting doubly linked list

[Jim Todhunter]

In article <OLSON.91May13142102 at sol.aaet.csc.ti.com> olson at aaet.csc.ti.com (Doug Olson) writes:
>I have a number of doubly linked lists of the type s_double_list,
>which is defined as:
>
>typedef struct double_list
>{
>  void *next;
>  void *prev;
>  char *key;
>} s_double_list;
>
>
>I need an efficient method of sorting these lists based on the key
>field. Any help would be greatly appreciated.

Not to sound trite, but building your list in sorted order in the first place
would allow you disperse the cost ( O(n2) ) of sorting over the run cycle of
your program.  However, if you must sort this pre-built structure:

  For small lists (less than 100-200 elements), simply pulling each node off the
  list and inserting into a new list should be fast enough ( O(n2) with a small
  overhead cost).

  For larger lists, you might try pulling each node off the list, and building a
  binary tree using next and prev as child pointers.  After the tree has been
  built, you can generate the newly sorted linked list by traversing the tree.
  This technique will provide O(n log n) performance at a modest overhead cost.

The implementation of either of the above methods is fairly simple.
-- 
 James W. Todhunter    |  ..uunet!merk!uvmark!jim
 Vmark Software, Inc.  |  Phone: 508-655-3700
 5 Strathmore Road     |  Fax:   508-655-8395
 Natick, MA  01760     |  Telex: 5101011619 VMARKUNIVERS