Chapter 5. Sorting Algorithms

Sorting from the LLP perspective: every comparison-based sort solves a forbidden-index problem on the inversion-vector lattice.

This page: LLP forms. View classical forms »

LLP-Sort-Adjacent: forbidden = inversion

LLP-Sort-Adjacent keeps the array $A$ itself as its state vector: index $j$ is forbidden when $A[j] > A[j+1]$ (an inversion at the seam $(j, j+1)$), and the advance rule swaps $A[j]$ and $A[j+1]$. The fixed point is the sorted array.

Time complexity: $O(n^2)$, where $n$ is the size of the array.

LLP-Sort-Pairwise

A more eager LLP form: $j$ is forbidden when some $k > j$ exists with $A[j] > A[k]$. The advance picks such a $k$ and swaps. Same fixed point as LLP-Sort-Adjacent but a different schedule.

Time complexity: $O(n^2)$, where $n$ is the size of the array.

MergeSort

The LL form of MergeSort. It uses the parallel-composition operator [ A [] B ] for the two recursive halves, then a sequential Merge on the combined range. In the sequential companion site we realise [ A [] B ] as A; B — the two recursions run one after the other. The parallel form lives in Chapter 10 with [] retained. An equivalent classical formulation is on the classical companion page.

Time complexity: $O(n \log n)$, where $n$ is the size of the array.

void sort(int lo, int hi, int[] G) {
  if (lo < hi) {
    int mid = (lo + hi) / 2;
    sort(lo, mid, G); sort(mid+1, hi, G);   // [] becomes ; in the sequential setting
    Merge(lo, mid, hi, G);
  }
}

void Merge(int lo, int mid, int hi, int[] G) {
  int[] B = new int[G.length];
  forall k in [lo..hi] : B[k] = G[k];
  int i = lo;  int j = mid + 1;  int k = lo;
  while (i <= mid && j <= hi) {
    if (B[i] <= B[j]) { G[k] = B[i]; i = i + 1; }
    else              { G[k] = B[j]; j = j + 1; };
    k = k + 1;
  };
  while (i <= mid) { G[k] = B[i]; i = i + 1; k = k + 1; };
  while (j <= hi)  { G[k] = B[j]; j = j + 1; k = k + 1; }
}

QuickSort

The LL form of QuickSort. Partition first, then run the two recursive calls on the resulting halves in parallel via [ ... [] ... ]. In the sequential companion site we realise [] as ; — the two recursions run one after the other. The partition step is the standard Lomuto scheme (pivot = rightmost element). The parallel form with [] retained lives in Chapter 10; an equivalent classical formulation is on the classical companion page.

Time complexity: $O(n^2)$ worst case, $O(n \log n)$ on average, where $n$ is the size of the array.

void sort(int lo, int hi, int[] G) {
  if (lo < hi) {
    int p = Partition(lo, hi, G);
    sort(lo, p - 1, G); sort(p + 1, hi, G);   // [] becomes ; in the sequential setting
  }
}

int Partition(int lo, int hi, int[] G) {
  int pivot = G[hi];
  int i = lo - 1;
  int j = lo;
  while (j <= hi - 1) {
    if (G[j] <= pivot) {
      i = i + 1;
      int tmp = G[i];
      G[i] = G[j];
      G[j] = tmp;
    };
    j = j + 1;
  };
  int tmp = G[i + 1];
  G[i + 1] = G[hi];
  G[hi] = tmp;
  return i + 1;
}

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[i]$ represents and the negation of the forbidden clause from the matching .llp source.