[ukoki]

Only the median (or pair around the median) needs to be sorted, the other numbers can be unsorted :)

[AdieuToLogic]

How does one determine the median wherein "the other numbers can be unsorted"?

To wit, given the unordered set:

  [ 5, 1, 3 ]

How would "Only the median (or pair around the median) needs to be sorted" be satisfied?

[salamanderman]

https://en.wikipedia.org/wiki/Quickselect

[AdieuToLogic]

From the Wikipedia page cited:

  As with quicksort, quickselect is generally implemented as 
  an in-place algorithm, and beyond selecting the kth 
  element, it also partially sorts the data.

When the above is applicable, those quickselect implementations would violate the original assertion of:

  Only the median (or pair around the median) needs to be 
  sorted, the other numbers can be unsorted

When the collection involved is immutable.