Модифицированная версия сортировки слияния, которая использует сортировку вставки

Question

После того, как я разделил массив, используя сортировку слияния, до тех пор, пока массив не будет иметь длину k, я должен использовать сортировку вставки в массиве длины k, а затем продолжить слияние. Какое должно быть оптимальное значение k?

Кроме того, я нашел эти вопросы, подобные моим, но не нашел однозначного ответа Choosing minimum length k of array for merge sort where use of insertion sort to sort the subarrays is more optimal than standard merge sort Modification to merge sort to implement merge sort with insertion sort Java

Answer 1

Это я чувствую, был более правильным ответ на мой вопрос http://atekihcan.github.io/CLRS/P02-01/, цитируя его здесь,

Для модифицированного алгоритма, чтобы иметь то же асимптотическое время работы в качестве стандартных сортировок слияния,

Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk) 

должен быть так же, как

Θ(nlgn). 

Чтобы удовлетворить это условие, к не может расти быстрее, чем lg⁡n асимптотический (если к растет быстрее, чем lg⁡n, из-за термин пк , алгоритм будет работать в худшее асимптотическое время, чем Θ (nlgn). Но этого аргумента недостаточно, так как нам нужно проверить на наличие

k=Θ(lgn), 

Требование выполнено или нет.

Если мы предположим,

k=Θ(lgn), 

Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)=Θ(nlgn+nlgn−nlg(lgn))=Θ(2nlgn−nlg(lgn))†=Θ(nlgn) 

† Lg (LGN) очень мала по сравнению с ЛГН при достаточно больших значениях п.

Answer 2

Просто измерить.

Наилучшее значение порогового значения зависит от вашего языка программирования, типа данных, распределения заданных значений daata, аппаратного обеспечения компьютера, сведений о деталях сортировки и добавления вставки и т. Д.

Обычно это значение находится в диапазоне 10-200, а коэффициент усиления для наилучшего значения не очень значителен.