[gclist] Sorting a doubly linked list.

Colvin, Greg Greg@imr.imrgold.com
Tue, 03 Dec 96 09:32:06


  >Does anyone know the best algorithm for sorting a doubly linked list without 
  >allocating a lot more storage.
  
  I use a variation on merge sort, similar to Knuth, 5.2.4. Algorithm L, but 
  using a natural merge instead of a strait merge, and using recursion instead 
  of auxiliary list heads.  Natural merge takes good advantage of existing 
  order.