A reference implementation of the Randomized Selection algorithm

The randomized selection algorithm can be used to find the kth smallest/largest element in an unsorted array. It is supported by the partition function used by quicksort.

class RandomizedSelection {
    static int select(List<Integer> ints, int k){
        Objects.requireNonNull(ints);
		if (k < 0 || k >= ints.size()) throw new IllegalArgumentException();
        return select(ints, 0, ints.size() - 1, k);
    }

	// We could instead order the list in descending order, making the split decision easier to read.
    private static int select(List<Integer> ints, int l, int r, int k){
        int finalPivotPos = partition(ints, l, r, (r + l) >>> 1); 
        int largerElements = r - finalPivotPos;
        if (largerElements > k){
            return select(ints, finalPivotPos + 1, r, k);  
        } else if (largerElements < k){
            return select(ints, l, finalPivotPos - 1, k - largerElements - 1);
        }
        return ints.get(finalPivotPos);
    }

    private static int partition(List<Integer> ints, int from, int to, int pivotPosition){
        int pivot = ints.get(pivotPosition);
        Collections.swap(ints, to, pivotPosition);
        int bound = from;
        for(int i = from; i <= to; i++){
            if(ints.get(i) < pivot){
                Collections.swap(ints, bound, i);
                bound++;
            }   
        }
        Collections.swap(ints, bound, to);
        return bound;
    }
}