Nothing special here. It’s just a blog post for summarising my algorithm learning course. Although this was already taught in the University, I remember nothing about it because I haven’t touched it for the long time.

Quick Sort - Duplicate Keys Problem

  • Quick Sort goes quadratic unless partitioning stops on equal keys!
  • ~½N2 compares when all keys equal.
  • B A A B A B B B C C C
  • A A A A A A A A A A A
  • Solve by using 3-way partitioning

3-way Partitioning

Partition array into 3 parts so that:

  • Entries between lt and gt equal to partition item v
  • No larger entries to left of lt
  • No smaller entries to right of gt


  • Let v be partitioning item a[lo]
  • Scan i from left to right.
    • (a[i] < v): exchange a[lt] with a[i]; increment both lt and i
    • (a[i] > v): exchange a[gt] with a[i]; decrement gt
    • (a[i] == v): increment i

Java Implementation

private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt)
        int cmp = a[i].compareTo(v);
        if (cmp < 0) exch(a, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else i++;
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);


Quick Sort with 3-way partitioning is even shorter (and harder to imagine). I gave one compliment to the brain that could thought of those above solutions.