gistfile1.java

private static void threeWayQuickSort(int[] a, int lo, int hi)
    {
        if (hi <= lo) return;

        int i = lo;
        int lessThan = lo;
        int greaterThan = hi;
        int pivot = a[lo];

        while (i <= greaterThan)
        {
            if (a[i] < pivot) {
                swap(a, lessThan++, i);
            } else if (a[i] > pivot) {
                swap(a, greaterThan--, i);
            } else {
                i++;
            }
        }

        threeWayQuickSort(a, lo, lessThan);
        threeWayQuickSort(a, greaterThan+1, hi);
    }