22 ms·

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

• AdieuToLogic 2mo ago
  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 2mo ago
    https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect
    • AdieuToLogic 2mo ago
      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.