Ну давайте прикинем сложность этого алгоритма. В среднем, мы на каждой итерации будем брать половину списка до тех пор, пока там не станет k элементов, после чего просто выдадим их.
Итого мы сделаем операций: N + N/2 + N/4 +..+k, что не превосходит 2N, так что асимптотическая сложность — O(N).
Разумеется, все мои рассуждения не точны, но, думаю, суть ясна. Да, есть худший случай, где оно работает примерно за O(N^2-k^2), но это беда qsort'а. В среднем время работы линейно.
Ну почему же? Можно, к примеру, сортировать qsort'ом, и при каждом разбиении идти только в меньшую половинку(за исключением случая, когда там мало элементов).
Итого мы сделаем операций: N + N/2 + N/4 +..+k, что не превосходит 2N, так что асимптотическая сложность — O(N).
Разумеется, все мои рассуждения не точны, но, думаю, суть ясна. Да, есть худший случай, где оно работает примерно за O(N^2-k^2), но это беда qsort'а. В среднем время работы линейно.
А я минут 10 думал. К черту универ, пойду в детский сад!
Погуглил бегло, все они какие-то попсовые и, на первый взгляд, неудобные.