src/vs/base/common/arrays.ts/quickSelect
export function quickSelect<T>(nth: number, data: T[], compare: Compare<T>): T {

	nth = nth | 0;

	if (nth >= data.length) {
		throw new TypeError('invalid index');
	}

	const pivotValue = data[Math.floor(data.length * Math.random())];
	const lower: T[] = [];
	const higher: T[] = [];
	const pivots: T[] = [];

	for (const value of data) {
		const val = compare(value, pivotValue);
		if (val < 0) {
			lower.push(value);
		} else if (val > 0) {
			higher.push(value);
		} else {
			pivots.push(value);
		}
	}

	if (nth < lower.length) {
		return quickSelect(nth, lower, compare);
	} else if (nth < lower.length + pivots.length) {
		return pivots[0];
	} else {
		return quickSelect(nth - (lower.length + pivots.length), higher, compare);
	}
}