1

Идея заключается в том, чтобы реализовать сортировку слиянием, в которой n/k подмассивов длиной k сортировались вставкой, после чего объединялись обычным слиянием. В наихудшем случае модифицированный алгоритм выполняется за O(nlog(n/k) + nk). Обычный же алгоритм слияния в наихудшем случает дает O(nlogn). Подскажите, пожалуйста, как подобрать оптимальное k?

2
  • 1
    Методом научного тыка. А вообще в java для timsort пороговое значение в 64 элемента установлено. Подозреваю, что оптимальное значение гдет-то рядом, в зависиоти от задачи и языка 27 июл 2019 в 21:16
  • 2
    да, да, вы заново изобрели ru.wikipedia.org/wiki/Timsort 27 июл 2019 в 21:28

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Посмотрите другие вопросы с метками или задайте свой вопрос.