alt Hacker NewsI 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)
Never mind, you're keeping the parts that are going to end up in that sorted location. That makes sense.
This visualisation made it click for me: https://www.youtube.com/watch?v=HylYYer2hR4