Черный ящик

Question

Предположим, у нас есть загадочная машина, которая возвращает медианное значение $m$ данного набора $S$ и установить $S/\{m\}$ в постоянное время, где $S/\{m\}$ обозначает разницу $S$ и элемент $m$. Докажите, что мы можем отсортировать любой список$n$элементы в линейное время с помощью такой машины. (допускается дополнительное пространство)

Вот моя идея, которая работает интуитивно правильно, но не может доказать ее математически:

Создайте новый массив с $n$ элементы и назначьте медианное значение $m$ оригинального набора $S$до середины массива. На каждой итерации мы ставим новую медиану$S/\{m\}$справа или слева от недавно использованного элемента: если он был слева, поместите новую медиану слева от этого элемента, и аналогично для самого правого элемента. Однако я не мог подумать, как здесь возможно математическое доказательство. Будем рады вашим исчерпывающим доказательствам этой проблемы.

Примечание. Если количество элементов четное, медиана определяется как меньшее среднее число.

Answer 1

Этот ответ предполагает, что вы знаете $n$ заранее, но можно адаптировать к общему случаю.

Sort(S)
  n ← length(S)
  T ← {1,...,n}
  A ← new array of length n
  repeat n times:
    S, m_S = extract_median(S)
    T, m_T = extract_median(T)
    A[m_T] = m_S
  end repeat
  return A

Идея здесь в том, что многократное извлечение медианы выведет элементы $S$ отсортированы в фиксированном порядке, который зависит только от $n$. Мы можем определить порядок, запустив тот же процесс для набора индексов$\{1,\ldots,n\}$.