Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!att!pacbell.com!decwrl!uunet!ontek!mikey
From: mikey@ontek.com (michelle (krill of yore) lee)
Newsgroups: comp.lang.c
Subject: Re: Sorting Double Linked List in place
Message-ID: <1558@ontek.com>
Date: 9 Nov 90 18:17:19 GMT
References: <1990Nov7.160701.5838@bkj386.uucp>
Organization: Ontek Corporation -- Laguna Hills, California
Lines: 19

In comp.lang.c, anton@analsyn.UUCP (Anton Aylward) writes:
| I'm looking for a routine to sort a double linked list in place, 
| given the head of the list and a compare function for the elements 
| (sort of like qsort).
| 
| I've seen single link sorts that use auxillary 'bins" (kind of like 
| merge tape sort), but I'm convinced ther is something more efficient 
| for the DLL, since there is the extra link.  
| 
| References or sample algorithm anyone ?

  What I always do is count how big the list is, malloc an array
  of pointers, initialize the array to point to each thing on the
  list, call qsort on the array, relink the list based on what
  comes back from qsort, and then free the array.  This consists of
  two passes + whatever length of time qsort takes.  Now you have
  a sorted, doubly linked list.

	the krill, or was that obvious?