Sorting Double Linked List in place

[John D. Mitchell]

In article <1930 at necisa.ho.necisa.oz> boyd at necisa.ho.necisa.oz (Boyd Roberts) writes:
>In article <1990Nov7.160701.5838 at bkj386.uucp> anton at analsyn.UUCP (PUT YOUR NAME HERE) 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).
>
>What about a bubble sort?
>
Call this whatever you want:

Assumptions:
	Linked list

typedef struct LList_
  {
  struct LList_ *prev;
  struct LList_ *next;
  void *data;			/* Whatever...	*/
  }  LList;

LList LLSort (LList *head)
  {
  LList *lessList,		/* List containing all those < pivot.	*/
	*morequalList;		/*  "     "         "   "   >=   "  .	*/
  LList *tmpList;

  /* Stopping case checks....	*/
  ....

  /* Partition the list.	*/
  /* Basically the trick is to find a good pivot.  Just run down the
   * current list placing any node < pivot into one list and everthing
   * else into the other list.
   */
  partitionList (&lessList, &morequalList);

  /* Sort each sub-list.	*/
  LLSort (lessList);
  LLSort (morequalList);

  /* Hook the sorted sub-lists together.	*/
  tmpList = lessList;
  while (tmpList->next)
    tmpList = tmpList->next;
  tmpList->next = morequalList;

  return (lessList);
  }


PLEASE note that the above is just for illustrative puposes.  I have
actual working code that does this somewhere :-).  There are all sorts
of things that you can "optimize" for many typical cases.  Pivot
selection is the toughest (personally I use circular doubly-linked
lists, so I use the mean of the first and last elements).  If you
might have many duplicates then adding an equal list can save
re-processing all of them needlessly. ....  This should get you
started :-)...

Good luck,
	John Mitchell
	johnm at cory.Berkeley.EDU