3-Way Quicksort

1void sort(int[] a, int lo, int hi) {2  if (lo >= hi) return;3  int pivot = a[lo], lt = lo, i = lo + 1, gt = hi;4  while (i <= gt) {5    if (a[i] < pivot) swap(a, lt++, i++);6    else if (a[i] > pivot) swap(a, i, gt--);7    else i++;  // duplicates settle here — never recursed into8  }9  sort(a, lo, lt - 1);10  sort(a, gt + 1, hi);11}