In-place quicksort woes

Question

I've been struggling with this for too many hours now. I'm trying to build an in-place quicksort in Java following a pseudocode example. Yes, I've tried implemented the example verbatim, but it's got an infinite loop problem. But anyway the logic seems sound, so I've been wrestling with fixing it for hours.

I can't for the life of me get the darn thing to work - here's an SSCCE using a trivial list: 15, 12, 13. Things sort when I expect them, but then the sub-lists are not split correctly. If I remove pointers in the swap area, duplicates are not supported. Can someone help out, or point me to a similar implementation that works (for which I've looked unsuccessfully)?

SSCCE, no traces:

import java.util.Arrays;
import java.util.List;

public class Quicksort {
public static void main(final String[] args0) {
    List<Integer> unsorted = Arrays.asList(new Integer[]{15, 12, 13});

    int size = unsorted.size();
    int left = 0;
    int right = size - 1;
    int pivot = 13; // Median of first, middle, last. Method removed for brevity.

    while (left < right) {
        while (unsorted.get(left).compareTo(pivot) < 0) {
            left++;
        }

        while (unsorted.get(right).compareTo(pivot) > 0) {
            right--;
        }

        if (unsorted.get(left).compareTo(unsorted.get(right)) > 0) {
            int old = unsorted.get(left);
            unsorted.set(left, unsorted.get(right));
            unsorted.set(right, old);

            if (left + 1 < size) {
                left++;
            }
            if (right - 1 >= 0) {
                right--;
            }
        }           
    }

    System.out.println("List: " + unsorted);
    System.out.println("Sublist left: " + unsorted.subList(0, left));  // Yields [13, 15] 
    System.out.println("Sublist right: " + unsorted.subList(left, size)); // Yields [12]
    // ...then recurse for sublists.
}
}

---

SSCCE, with traces (same as above):

import java.util.Arrays;
import java.util.List;

public class Quicksort {
public static void main(final String[] args0) {
    List<Integer> unsorted = Arrays.asList(new Integer[]{15, 12, 13});

    int size = unsorted.size();
    int left = 0;
    int right = size - 1;
    int pivot = 13; // Median of first, middle, last. Method removed for brevity.

    System.out.println("---Processing " + unsorted);
    System.out.println("Median " + pivot);
    System.out.println("Left = " + left + ", right = " + right);

    while (left < right) {
        System.out.println("Start INC/DEC, left = " + left + ", right = " + right);
        while (unsorted.get(left).compareTo(pivot) < 0) {
            left++;
        }

        while (unsorted.get(right).compareTo(pivot) > 0) {
            right--;
        }
        System.out.println("End INC/DEC, left = " + left + ", right = " + right);

        if (unsorted.get(left).compareTo(unsorted.get(right)) > 0) {
            int old = unsorted.get(left);
            unsorted.set(left, unsorted.get(right));
            unsorted.set(right, old);

            if (left + 1 < size) {
                left++;
            }
            if (right - 1 >= 0) {
                right--;
            }

            System.out.println("End swap, left = " + left + ", right = " + right + ", list now " + unsorted);
        }           
        System.out.println("End while, left = " + left + ", right = " + right + ", list now " + unsorted);
    }

    System.out.println("List: " + unsorted);
    System.out.println("Sublist left: " + unsorted.subList(0, left));
    System.out.println("Sublist right: " + unsorted.subList(left, size));
    // ...then recurse for sublists.
}
}

Answer 1

It seems that you compare values before swapping:

if (unsorted.get(left).compareTo(unsorted.get(right)) > 0)

while the reference code compares indices:

if left ≤ right

Also see the difference in comparison: <= instead of >.