Sorting and Searching Linked Lists in Java

Dr. Dobbs Journal, May 1998, Algorthm Alley, by John Boyer.

// Merge subroutine used by the following
private void merge(Node before, Node F1, int N1, 
                   Node F2, int N2, NodePair NP) {
  Node first = null, last = null, temp = null;
  int I,J;
  first = last = F1.compareTo(F2) <= 0 ? F1 : F2;
  for (I = J = 0; I < N1 || J < N2; ) {
    if (I < N1 && (J >= N2 || F1.compareTo(F2) <= 0)) {
      temp = F1; F1 = F1.next; I++; }
    else {
      temp = F2; F2 = F2.next; J++; }
    last.next = temp;
    last = temp;
    }
  if (before = null) 
    First = first
  else
    before.next = first;
  last.next = F2;
  NP.first = first;
  NP.last = last;
  }

// Simple non-recursive Merge Sort
private void mergesort() {
  int i, j, k, N1, N2;
  Node F1, F2, before;
  NodePair NP = new NodePair();
  for (i = 1; i < NumNodes; i <<= 1) { // the { is not required here
    for (before = null, N1 = N2 = i, j = 0; j+n1<NumNode; j += i << 1) {
      F1 = F2 = before == null ? First : before.next;
      for (k = 0; k < N1; k++) F2 = F2.next; // move F2 to [N1]
      if (N2 > NumNodes - j - N1) N2 = NumNodes - j - N1; // limit N2
      merge(before, F1, N1, F2, N2, NP);
      before = NP.last;
      }
    }
  }

// Singly Linked List Recursive Merge Sort
private void mergesort(node before, Node F1, int N1, NodePair NP) {
  if (N1 <= 1)
    NP.first = NP.last = F1;
  else {
    Node F2;
    int N2;
    N2 = N1; N1 >>= 1; N2 -= N1;
    mergesort(before, F1, N1, NP);
    F1 = NP.first;
    F2 = NP.last.next;
    mergesort(NP.last, F2, N2, NP);
    F2 = NP.first;
    merge(before, F1, N1, F2, N2, NP);
    }
  }

// Singly Linked List Binary Search
public Node binarySearch(Object SearchKey) {
  Node PartitionFirst = First, MidPtr = nul;
  int Partition Size = NumNodes, Mid, I, Result;
  while (PartitionSize > 0) {
    Mid = PartitionSize / 2;
    MidPtr = PartitionFirst;
    for(I = 0; I < Mid; I++)
      MidPtr = MidPtr.next;
    Result = MidPtr.compareTo(SearchKey);
    if (Result > 0)
      PartitionSize = Mid;
    else if (Result < 0) {
      PartitionSize -= Mid;
      PartitionFirst = MidPtr;
      }
    else return MidPtr;
    }
  return null;
  }

Linked list Quicksort

Uses first node's key as the pivot. Traverses forward through the list using two references called aNode and aNodePrev. Nodes with a key value greater than or equal to the pivot are ignored. When a node containing a lesser key is encountered, the code deletes aNode by connecting aNodePrev.next to aNode.next. Then aNode is pushed onto the front of the list, becoming the new first node and the remaining nodes of the list are traversed or transferred to the front in the same manner. At the end of this process,  the list is divided into two sublists, which can be recursivly sorted by applying this partitioning procedure to each sublist.

//Singly Linked List Quicksort
private Node QuickSort(Node before, Node first, int n) {
  int Num1=0, Num2=n, i=1;
  Node Pivot=first, aNode=first, aNodePrev=first;
  // Pivot Advancement
  for (i=1; i<n; i++, aNode=aNode.next) {
    if (aNode.compareTo(aNode.next) > 0)
      break;
    if ((i&1)==0) { //every other time through the loop
      Pivot=Pivot.next;
      Num1++;
      }
    }
  //Recognize sortedness in linear time
  if (i == n) return first; //Pivot advanced through entire list and found it to be aleady sorted
  // Partition list by unlinking nodes with values less 
  // than the pivot and pushing them onto front of list
  for (aNodePrev = aNode; i < n; i++) {
    aNodePrev.next = aNode.next;
    if (Pivot.compareTo(aNode) > 0) {
      aNode.next = first;
      first = aNode;
      Num1++;
      }
    else aNodePrev = aNode;
    }
  if (before!=null) before.next = first;
  Num2 = n - Num1 - 1;
  // Recurse to sort sublists
  if (Num1 > 1) first = QuickSort(before, first, Num1);
  if (Num2 > 1) QuickSort(Pivot, Pivot.next, Num2);
  return first;
  )