alt Hacker NewsI just discovered the name of this. I visualized that you can do a quicksort but only recurse one of the partitions each time--the one that contains the median index. It has the same worst-case O(n^2) and can be fixed the same way choosing the median pivot of 3 potential pivots. Apparently C++'s `std::nth_element` uses quick-select and since if you choose a different target index can find any percentile not just the median.
I assume that "index" in this case is for the index in the fully sorted list? i.e. if you're looking for the 50th place in a 100 item list, then it's 50th place in the sorted list you want.
But as you don't know what value that is, how do you know which partition it's in?
(I am feeling very stupid today and hoping someone can explain this to me)