10.1.9. Sorting a Linked List

A simple but inefficient sorting algorithm: Insertion Sort

---

A previous page defines function insert, where insert(x, L) does a destructive insert of x into sorted lists L. (We assume that "sorted" means in nondescending order.) To sort a list, it suffices to insert the head of the list into the sorted version of the tail. Here is a function that does that job, using insert.

  // insertionSort(L) sorts linked list L and returns the
  // sorted list.  List L is not modified.  The sorted list
  // is made from new list cells.

  List insertionSort(List L)
  {
    if(isEmpty(L))
    {
       return emptyList;
    }
    else
    {
       List T = insertionSort(tail(L));
       insert(head(L), T);
       return T;
    }
  }

Suppose that list L has n members. Then insertionSort will do n calls to insert. One of them will insert into an empty list, another will insert into a list of length 1, another into a list of length 2, etc.

The time to do in insert into a list of length k is proportional to k. Let's say it is k + 1, since that is the number of cells in the list that insert produces. (If the original list is in descending order, then each insert will need to insert at the end.) So the total time to sort a list of length n must be some constant times 1 + 2 + ... + n = n(n+1)/2.

To summarize, insertionSort takes time Θ(n²) in the worst case.

An efficient sorting algorithm: merge sort

---

We can do much better. To sort a nonempty list L of length n, break L into halves, where L₁ is the first half and L₂ is the second half. Sort lists L₁ and L₂. So now we have two sorted lists. All that is left to do is to merge those lists together into a single sorted list, taking advantage of the facts that they are already sorted. The resulting algorithm, called Merge Sort, can be shown to take time Θ(n log₂(n)) in the worst case.

The following is an implementation of Merge Sort.

/*======================================================*
 *			length				*
 *======================================================*
 * length(L) returns length list L.			*
 *======================================================*/

int length(List L)
{
  int count = 0;

  for(List p = L; p != NULL; p = p->tail) 
  {
    count++;
  }
  return count;
}

/*======================================================*
 *			merge				*
 *======================================================*
 * merge(A,B) requires that lists A and B are already   *
 * in nondescending order.  It merges them into a single*
 * list in ascending order and returns that list.       *
 *							*
 * NOTE: This function does not allocate new list cells.*
 * It reorders the cells that make up lists A and B.    *
 * After merge(A,B), lists A and B have been destroyed  *
 * to make the sorted list.				*
 *======================================================*/

List merge(List A, List B)
{
  if(A == NULL)
  {
    return B;
  }
  else if(B == NULL)
  {
    return A;
  }
  else if(A->head < B->head)
  {
    A->tail = merge(A->tail, B);
    return A;
  }
  else
  {
    B->tail = merge(A, B->tail);
    return B;
  }
}

/*======================================================*
 *			mergesort			*
 *======================================================*
 * mergesort(L,n) reorders the first n members of list  *
 * L into ascending order, and returns that list.  It   *
 * sets parameter L to point to the remainder of the    *
 * original list L, after the first n members.		*
 *							*
 * For example, if L = [5,2,3,6,4], then		*
 *   mergesort(L,3)					*
 * returns [2,3,5] and sets L = [6,4].			*
 *							*
 * NOTE: This function rearranges the first n list 	*
 * list cells.  It does not create new cells.		*
 *======================================================*/

List mergesort(List& L, int n)
{
  if(n == 0)
  {
    return NULL;
  }
  else if(n == 1)
  {
    List p = L;

    L = L->tail;
    p->tail = NULL;
    return p;
  }
  else
  {
    int  m = n/2;
    List A = mergesort(L, m);
    List B = mergesort(L, n-m);
    return merge(A,B);
  }
}

/*======================================================*
 *			sortlist			*
 *======================================================*
 * sortlist(L) sorts list L into ascending order by	*
 * rearranging the cells.				*
 *======================================================*/

void sortlist(List& L)
{
  L = mergesort(L, length(L));
}