QuickSort Three Way Partition + Hybrid Implementation

Question

I am trying to implement a Three Way Partition QuickSort using a Hybrid QuickSort. The problem is that I am getting an unordered list at the end. I've tested the Hybrid QuickSort and Insertion Sort on their own and they work perfectly (tested for sizes: 10, 50, 500, 1000, 5000). I run debug and can't still tell what the problem is. Thank you in advance. Here is the code.

public <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
    int lo = 0;
    int hi = list.size() - 1;

    if (hi <= lo) return;
    int lt = lo, i = lo+1, gt = hi;
    while (i <= gt) {
        if (comparator.compare(list.get(i), list.get(lo)) < 0) //did not use AbstractSorter greter in order to check all cases.
            exch(list, lt++, i++);
        else if(comparator.compare(list.get(i), list.get(lo)) > 0)
            exch(list, i, gt--);
        else
            i++;
    }  // Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
    sort(comparator, list, lo, lt - 1);
    sort(comparator, list, gt + 1, hi);
}

private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi){
    if(hi <= lo) return;
    if(hi - lo <= 8){
        InsertionSort sorter = new InsertionSort();
        sorter.sort(comparator, list.subList(lo, hi + 1));
        List<SorterListener> listeners = (ArrayList)sorter.getListeners();
        for(SorterListener s: listeners)
            getListeners().add(s);
        return;
    }
    int i = partition(comparator, list, lo, hi);
    sort(comparator, list, lo, i - 1);
    sort(comparator, list, i + 1, hi);
}

Edit:

public <T> void exch(@NotNull List<T> list, int i, int j) {
    final T aux = list.get(i);
    list.add(i, list.get(j));
    list.remove(i + 1);
    list.add(j, aux);
    list.remove(j + 1);
    listeners.get(0).swap(i, j);
}


public <T> int partition(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi) {
    int i = lo - 1;
    int j = hi;
    while(true) {
        while( greater(list, hi, ++i, comparator)) //find item left to swap
            if (i == hi) break;
        while( greater(list, --j, hi, comparator)) //find item right to swap
            if (j == lo) break;
        if (i >= j) break; //check if pointers cross
        exch(list, i, j); //swap
    }
    exch(list, i, hi); //swap with partitioning item
    return i; //return index of item now known to be in place
}

Answer 1

If I understand your intent in the partitoning in the first sort method (the public one), lt points to the element you are partitioning by. So in your comparisons, you should compare the element at i with the element at lt, not the one at lo:

    if (comparator.compare(list.get(i), list.get(lt)) < 0) //did not use AbstractSorter greter in order to check all cases.
        exch(list, lt++, i++);
    else if(comparator.compare(list.get(i), list.get(lt)) > 0)
        exch(list, i, gt--);

With this change the method seems to work correctly, at least on the samples I have run it on.

BTW, your comment helped me, Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. You can do even better by transforming it into assertions:

    T v = list.get(lt);
    for (int ix = lo; ix < lt; ix++) {
        assert comparator.compare(list.get(ix), v) < 0 : "lt " + lt + ' ' + list;
    }
    for (int ix = lt; ix <= gt; ix++) {
        assert comparator.compare(list.get(ix), v) == 0 : "lt " + lt + " gt " + gt + ' ' + list;
    }
    for (int ix = gt + 1; ix <= hi; ix++) {
        assert comparator.compare(list.get(ix), v) > 0 : "gt " + gt + ' ' + list;
    }

With these assertion enabled, Java will catch the error and print for instance:

Exception in thread "main" java.lang.AssertionError: gt 2 [1, 0, 3, 6, 4, 8, 9, 5, 2, 7, 10]

In this case gt points to the element 3, but there’s a 2 further to the right in the list.