Тим Сорт Часть слияния массивов

Question

предположим, что я получил эти целые числа 6,1,4,2,1,5,9,6,3,4, а размер прогона равен 2, поэтому мы начинаем с сортировки вставок для каждого прогона, и я получаю следующие вложенные массивы:

1-6, 2-4, 1-5, 6-9, 3-4

мой вопрос: как мне объединить их, чтобы получить отсортированный массив ??Я имею в виду, нужно ли объединять каждые два массива, а затем все остальные и т. Д. И т. Д.

Answer 1

После создания начальных прогонов вы затем объединяете прогоны.Timsort использует стек для отслеживания границ прогонов и использует 3 верхние записи в стеке, чтобы решить, какие прогоны объединить, чтобы «сбалансировать» объединения, сохраняя при этом «стабильность».Можно использовать очередь (FIFO) вместо стека (LIFO) (хотя я не уверен, что это будет технически временная сортировка).При 10 элементах размер прогона 3 займет на один проход меньше.Timsort обычно использует больший минимальный размер прогона, от 32 до 64 (включительно), используя сортировку вставкой, чтобы принудительно установить минимальный размер прогона, если естественный прогон меньше расчетного идеального минимального размера прогона.Ссылка на статью вики:

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