Quicksort implementation equivalent to Collections.sort()

Question

Here is my go at understanding generics, Comparables and Comparators, as well as type bounds. I believe I made it as close to Collections.sort as possible in terms of interface. Please review.

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class QuickSort {
    private static final Random rng = new Random();

    public <T extends Comparable<? super T>> void sort(List<T> xs) {
        sort(xs, 0, xs.size() - 1);
    }

    public <T> void sort(List<T> xs, Comparator<? super T> cmp) {
        sort(xs, 0, xs.size() - 1, cmp);
    };

    private static <T extends Comparable<? super T>>
    void sort(List<T> xs, int fst, int lst) {
        sort(xs, fst, lst, (x, y) -> x.compareTo(y));
    }

    private static <T>
    void sort(List<T> xs, int fst, int lst, Comparator<? super T> cmp) {
        if (fst >= lst) return;

        int i = fst, j = lst;

        T pivot = xs.get(rng.nextInt(xs.size()));

        while (i <= j) {
            while (cmp.compare(xs.get(i), pivot) < 0)
                i++;
            while (cmp.compare(pivot, xs.get(j)) < 0)
                j--;

            if (i <= j)
                Collections.swap(xs, i++, j--);
        }

        sort(xs, fst, j, cmp);
        sort(xs, i, lst, cmp);
    }
}

Answer 1

As far as your understanding of generics, I think you've pretty much got it.

On other matters:

• (x, y) -> x.compareTo(y) - that can be reduced to a function reference Comparable::compareTo. In this specific case, it's also available to you as Comparator.naturalOrder()
• You should double check your random number generator for getting your pivot. It looks to me like you're taking a pivot element from anywhere in the list, not in the sublist that you're sorting.