Quicksort implementation equivalent to Collections.sort() 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 &lt;T extends Comparable&lt;? super T&gt;&gt; void sort(List&lt;T&gt; xs) {
        sort(xs, 0, xs.size() - 1);
    }

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

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

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

        int i = fst, j = lst;

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

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

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

        sort(xs, fst, j, cmp);
        sort(xs, i, lst, cmp);
    }
}
As far as your understanding of generics, I think you've pretty much got it.

On other matters:


(x, y) -&gt; 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.