QuickSort for a List<T>

I want my QuickSort class to have a static sort method that sort any List for any object that extends Comparable. Have I coded my class correctly? Can I make the use of generics a bit cleaner or is this the only way to code the signatures of the methods?

import java.util.List;

public class QuickSort{

    private QuickSort() {
        // prevent instantiation
    }

    public static > void sort(List list) {
        quickSort(list, 0, list.size());
    }

    private static > void quickSort(List array, int start, int arrayLength){
        if(start > int partition(List array, int end, int arrayLength){
        T last = array.get(arrayLength-1);
        int i = end-1;
        for(int j = end; j > void exchange(int j, int i, List array){
        T temp = array.get(j);
        array.set(j, array.get(i));
        array.set(i, temp);
    }
}

Naming

QuickSort is not a simple algorithm, and naming things helps to make it more readable. Unfortunately, with descriptive names, if you name things wrong it makes it worse than if you you use cryptic names. Your recursive method is:

private static > void quickSort(List array, int start, int arrayLength){
    if(start < arrayLength){
        int q = partition(array, start, arrayLength);
        quickSort(array, start, q);
        quickSort(array, q+1, arrayLength);
    }
}

But, arrayLength does not mean array length, it means "end-exclusive", or "ignore-from" or something.

One of the common tricks in the quickSort is to use the actual index of the last element in the partition, instead of the length. For example, you call the method with:

quickSort(list, 0, list.size());

But, what if you called it with:

quickSort(list, 0, list.size() - 1);

Then named your parameters:

private static > void quickSort(
            List array, int start, int end) {

Now you have start and end, and you do not need to do the immediate offset adjustment in the partition method.

Now, with that simple adjustment, the code becomes more readable simply because the variables do what they say, and don't lie to you.
Exchange

Your exchange method is good, no major problems there (with some caveats though... we will get to those...)

exchange is a decent name, but convention would call it swap...., give it decent index names, and common convention would be to put the indices after the reference:

private static > void exchange(
        List array, int left, int right) ....

Partitioning

Note, your current partition method is:

private static > int partition(List array, int end, int arrayLength){
    T last = array.get(arrayLength-1);
    int i = end-1;
    for(int j = end; j < arrayLength-1; j++){
        if(array.get(j).compareTo(last) <= -1 || array.get(j).compareTo(last) == 0){
            i = i+1;
            exchange(j, i, array);
        }
    }
    exchange(arrayLength-1, i+1, array);
    return i + 1;
}

Notice what happens if we give it decent variable names, and use the 'end' instead of the arrayLength

private static > int partition(
        List array, int first, int last) {
    T key = array.get(last);
    int smaller = first - 1;
    for (int test = first; test < last; test++) {
        if (array.get(test).compareTo(key) <= 0) {
            smaller++;
            exchange(smaller, test, array);
        }
    }
    smaller++;
    exchange(last, smaller, array);
    return smaller;
}

For a start, notice the condition:

if (array.get(test).compareTo(key) <= -1
        || array.get(test).compareTo(key) == 0) {

can be reduced to just:

if (array.get(test).compareTo(key) <= 0) {

All values up to smaller are smaller or equal to key.

Your code makes some sense to me now.

Note, the algorithm you use to partition the data is a little unconventional... though I can't see a real problem with it.

A conventional approach would have a left and right index that progress from the ends, and then swap values from each side, and meet in the middle somewhere. Your approach is OK, though.
Putting it together

With these changes, putting it all together, you will need to change the calling routines:

public static > void sort(List list) {
    quickSort(list, 0, list.size() - 1);
}

private static > void quickSort(List array, int left, int right){
    if(left  >= right) {
        return;
    }
    
    int q = partition(array, left, right);
    quickSort(array, left, q - 1);
    quickSort(array, q + 1, right);
}

private static > int partition(
        List array, int first, int last) {
    T key = array.get(last);
    int smaller = first - 1;
    for (int test = first; test > void exchange(int j,
        int i, List array) {
    T temp = array.get(j);
    array.set(j, array.get(i));
    array.set(i, temp);
}

public static void main(String[] args) {
    List data = new ArrayList(System.getProperties().stringPropertyNames());
    sort(data);
    for (String d : data) {
        System.out.println(d);
    }
}

Foot Notes

Note that your code has horrible performance on List instances that are not random-access... Consider someone who feeds your code a LinkedList... it will perform badly because each time you get or set with an index, it has to scan the data for the value.

RandomAccess is an interface available on collections that support fast and easy index-based access.

The Java implementation solves sorting non-RandomAccess Lists by dumping all the data in to a different RandomAccess list, sorting that, and then copying it back again, something like:

if (list instanceof RandomAccess) {
    sort(list);
} else {
    List toSort = new ArrayList<>(list);
    sort(toSort);
    list.clear();
    list.addAll(toSort);
}

StackExchange Code Review Q#79508, answer score: 8