// Quicksort with 3-way partitioning
//    http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf

void quicksort(Item a[], int l, int r)
{
    int i = l-1, j = r, p = l-1, q = r;
    Item v = a[r];
    if (r <= l) return;
    for (;;)
    {
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
        if (a[i] == v) {
            p++;
            exch(a[p], a[i]);
        }
        if (v == a[j]) {
            q--;
            exch(a[j], a[q]);
        }
    }
    exch(a[i], a[r]);
    j = i-1;
    i = i+1;
    for (k = l; k < p; k++, j--) exch(a[k], a[j]);
    for (k = r-1; k > q; k--, i++) exch(a[i], a[k]);
    quicksort(a, l, j);
    quicksort(a, i, r);
}