K-ая порядковая статистика за O(N) в среднем случае

Потратил значительное время на поиск красивой реализации данного алгоритма. Как и следовало ожидать она лежала прямо под носом

1. int partition(vector<int> &mas, int l, int r) {
2.   if (l!=r)
3.     swap(mas[l + rand() % (r - l)], mas[r]);
4.   int x = mas[r];
5.   int i = l-1;
6.   for (int j = l; j <= r; j++) {
7.     if (mas[j] <= x)
8.       swap(mas[++i],mas[j]);
9.   }
10.   return i;
11. }
12. int nth(vector<int> mas, int n) {
13.   int l = 0, r = mas.size() - 1;
14.   for(;;) {
15.     int pos = partition(mas,l,r);
16.     if (pos < n)
17.       l = pos + 1;
18.     else if (pos > n)
19.       r = pos - 1;
20.     else return mas[n];
21.   }
22. }

* This source code was highlighted with Source Code Highlighter.

Немного проанализируем представленный код.
Функция nth принимает на вход массив и номер порядковой статистики, которую нужно найти. После выполнения функция возвращает значение порядковой статистики.
Но куда большее значение имеет функция partition. Суть ее заключается в том, что она выбирает произвольный элемент массива mas, индекс которого находится в интервале [l,r] и ставит его на “свое место”, т.е. на то место, на котором находился элемент, если бы массив был упорядочен.
В строке 3 как раз и происходит выбор этого произвольного элемента. После чего выбранный элемент меняется местами с последним элементом рассматриваемого интервала.
Если в качестве произвольного элемента брать всегда последний элемент или какой-нибудь фиксированный, то при желании можно легко подобрать тест, на котором представленная реализация будет иметь квадратичную сложность. Кстати если исходный массив будет упорядочен и в реализации функции partition будут отсутствовать 2 и 3 строки, то в каждой итерации функции nth на “свое место” будет становится только последний элемент и это будет повторяться SIZE раз, где SIZE – размерность массива.
На произвольном массиве данная реализация работает в среднем за O(N). Реализацию данного алгоритма при которой он будет работать за O(N) на любом массиве мы рассмотрим позже.

Обратите внимание, что в приведенной реализации массив передается по значению. Это следует делать, если мы незаинтересованы в частичном упорядочивании массива. В противном случае массив следует передавать по ссылке.

P.S: Если исходный массив будет состоять из одинаковых элементов, то приведенный алгоритм будет работать за O(N*N).