> You can definitely do this without sorting. > QuickSelect is ... Quickselect implementations can, and often do, partially sort the underlying collection:

> You can definitely do this without sorting. > QuickSelect is ... Quickselect implementations can, and often do, partially sort the underlying collection: As with quicksort, quickselect is generally implemented as an in-place algorithm, and beyond selecting the kth element, it also partially sorts the data.[0] If you are aware of a quickselect implementation having O(n) average performance which does not modify the underlying collection, I would very much appreciate a reference to same. 0 - https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect