Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!elroy.jpl.nasa.gov!decwrl!mcnc!duke!drh
From: drh@duke.cs.duke.edu (D. Richard Hipp)
Newsgroups: comp.lang.c
Subject: Re: Sorting Double Linked List in place
Message-ID: <658158129@juliet.cs.duke.edu>
Date: 9 Nov 90 13:42:11 GMT
References: <1990Nov7.160701.5838@bkj386.uucp> <14403@smoke.brl.mil>
Organization: Duke University Computer Science Dept.; Durham, N.C.
Lines: 109

Efficient code for in-place sorting a doubly linked list is attached.
------------------------------ cut here -------------------------------------

/*
** An entry in a doubly linked list
*/
typedef struct s_dbllink {
  int key;
  struct s_dbllink *prev, *next;
} dblink;

/*
** Merge sort on a linked list.  Only the "next" links are used -- the
** list is treated as if it were singly linked.
*/
void mergesort(dblink **topptr){
  dblink *left, *right, *top;

  top = *topptr;

  /* Only do the sort if there are 2 or more elements in the list. */
  if( top && top->next ){

    /* Step 1: Break the list into two roughly-equal sized parts. "right"
    ** and "left" will point to the head of each part */
    left = right = 0;
    while( top ){
      dblink *next;
      next = top->next;
      top->next = left;
      left = top;
      top = next;
      if( top ){
        next = top->next;
        top->next = right;
        right = top;
        top = next;
      }
    }
  
    /* Step 2: Recursively call mergesort to sort each half of the list */
    mergesort(&left);
    mergesort(&right);

    /* Step 3: Merge the two halves of the list back together */
    if( left->key<right->key ){  
      *topptr = top = left;
      left = left->next;
    }else{
      *topptr = top = right;
      right = right->next;
    }
    while( left && right ){
      if( left->key<right->key ){
        top->next = left;
        left = left->next;
      }else{
        top->next = right;
        right = right->next;
      }
      top = top->next;
    }
    top->next = left ? left : right;
  }
}

/*
** Sort a doubly linked list
*/
void dblsort(dblink **topptr){
  dblink *p, *x;

  /* Call mergesort to sort the list.  The "prev" links are ignored */
  mergesort(topptr);

  /* Reconnect the "prev" links */
  for(x=*topptr, p=0; x; x=x->next){
    x->prev = p;
    p = x;
  }
}

#ifdef TEST
#include <stdio.h>
#include <stdlib.h>

void main(void){
  char line[1000];
  dblink *x, *y;

  x = 0;
  printf("Enter numbers.  ^D to stop input.\n");
  while( fgets(line,1000,stdin) ){
    y = malloc( sizeof(dblink) );
    if( !y ) break;
    y->next = x;
    y->prev = 0;
    y->key = atoi(line);
    if( x ) x->prev = y;
    x = y;
  }
  dblsort(&x);
  printf("---------- forward -------------\n");
  for(y=x; y; y=y->next) printf("%d\n",y->key);
  printf("---------- backward ------------\n");
  for(y=x; y->next; y=y->next);
  for(; y; y=y->prev) printf("%d\n",y->key);
}
#endif