Как сортировка слиянием работает на массивах длины N?

Question

Я попал в книги и столкнулся с проблемой, которую не могу решить. Я долго искал информацию. Я сломал голову, пытаясь понять это.

Итак, мне дан массив длины N (int) для сортировки с использованием нерекурсивного алгоритма сортировки слиянием. Я выучил алгоритм сортировки слиянием для массивов длиной 2 ^ n. Но я совершенно не могу понять, как это работает для массивов длины N.

Может кто-нибудь объяснить мне, как это работает?

Answer 1

Учитывая семь элементов, дерево подзадач выглядит так:

          [3,5,2,1,4,7,6]
             /         \
      [3,5,2,1]        [4,7,6]
      /       \        /      \
   [3,5]    [2,1]    [4,7]    [6]
   /   \    /   \    /   \    /
 [3]  [5]  [2]  [1] [4]  [7] [6]

Идея состоит в том, что вы разбиваете массив «пополам» на каждом уровне. Если массив имеет нечетное количество элементов, то его разбиение приведет к тому, что в одном подмассиве будет еще один элемент, чем в другом. Это не делает проблему более сложной: объединение двух массивов разной длины не составит труда.

Answer 2

Нерекурсивная сортировка слиянием обрабатывает массив из N элементов как N отсортированных прогонов размером 1, затем объединяет четные и нечетные прогоны из одного массива в другой массив. Если есть нечетное количество запусков, последний только что скопирован (нечего объединять), об этом можно позаботиться в функции merge (). После завершения прохода слияния размер прогона удваивается до 2, и процесс слияния повторяется. Когда размер прогона удваивается и> = размер массива, сортировка слияния выполняется.

Код поддерживает 3 индекса: начало левого прогона, начало правого прогона (== конец левого прогона)конец правого забега. При настройке или продвижении индексов, если индекс становится> = размером массива, он уменьшается до размера массива. Если это происходит в левом прогоне, то это последний и нечетный прогон, поэтому он копируется (опять же, это может быть обработано в функции merge ()).

В Википедии есть псевдокод:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation