Comparison-Based Sorting

• merge sort O(nlogn)
• quick sort O(nlogn)
• heap sort O(nlogn)

compare(a,b)

• -1: a < b
• 0: a == b
• +1: a > b

Merge-Sort

is a classic recursive divide and conquer.

• if a is at most 1 then a is sorted.
• else we split a into two halves
  • a0 = a[0...(n/2)-1]
  • a1 = a[(n/2)...n-1]
  • merge a0, a1

void mergeSort(T[] a, Comparator<T> c) {
  if (a.length <= 1) return;

  T[] a0 = Arrays.copyOfRange(a, 0, a.length/2);
  T[] a1 = Arrays.copyOfRange(a, a.length/2, a.length);
  mergeSort(a0, c);
  mergeSort(a1, c);
  merge(a0, a1, a, c);
}

Quicksort

Unlike mergesort which does merging after solving the two subproblems, quicksort does all of its work upfront.

1. pick a random pivot element x from a
2. partition a into the set of elements less than x, the set of elements equal to x and the set of elements greater than x.
3. recursively sort the first and third sets in this partition.

void quickSort(T[] a, Comparator<T> c) {
  quickSort(a, 0, a.length, c);
}
void quickSort(T[] a, int i, int n, Comparator<T> c) {
  if (n <= 1) return;
  T x = a[i + rand.nextInt(n)];
  int p = i - 1, j = i, q = i+n;

  while (j < q) {
    int comp = compare(a[j], x);
    if (comp < 0) {
      swap(a, j++,  ++p);
    } else if (comp > 0) {
      swap(a, j, --q);
    } else {
      j++;
    }
  }
  quickSort(a, i, p-i+1, c);
  quickSort(a, q, n-(q-i), c);
}

Heap-sort

In-place sorting algorithm. Uses binary heaps. Binary heap data structure represents a heap in a single array. The heap sort converts the input array into a heap and then extracts the min value.

Counting sort and Radix sort

These are not comparison based sorting algorithms. These are specialized for sorting small integers.

Counting Sort

This algorithm sorts using an auxiliary array of counters. This is very efficient for sorting an array of integers when the length, n, of the array is not much smaller than the maximum value, k-1, that appears in the array.

int[] counting_sort(int[] a, int k) {
  int c[] == new int[k];
  for (int i = 0; i < a.length; i++)
    c[a[i]]++;
  for (int i = 1; i < k; i++)
    c[i] += c[i-1];
  int b[] new int[a.length];
  for (int i = a.length - 1; i >= 0; i--)
    b[--c[a[i]]] = a[i];
  return b;
}

Radix Sort

Uses several passes of counting-sort to allow for a much greater range of maximum values.

Sorts w-bit integers by using w/d passes of counting-sort to sort these integers d bits at a time.

i.e.

first sorts the ints by their least significant d bits, then their next significant d bits, and so on until, in the last pass, the ints are sorted by their most significant d bits.

int[] radixSort(int[] a) {
  int[] b = null;

  for (int p = 0; p < w/d; p++) {
    int c[] = new int[1<<d];
    b = new int[a.length];
    for (int i = 0; i < a.length; i++)
      c[(a[i] >> d*p)&((1<<d)-1)]++;
    for (int i = 1; i < 1<<d; i++)
      c[i] += c[i-1];
    for (int i = a.length - 1; i >= 0; i--)
      b[--c[(a[i] >> d*p)&((1<<d)-1)]] = a[i];
    a = b;
  }
  return b;
}