Почему его можно разделить между 82 и 10?

Question

Если у меня есть массив [9, 82, 10].Используя сортировку слиянием, я должен сравнить левый индекс с правым индексом, и если l 10. Я так растерялся.

Answer 1

Я думаю, вы путаете эту логику с другим алгоритмом (может быть, с быстрой сортировкой?), Потому что разделение происходит независимо от значений.Где происходит разделение, зависит только от текущей длины массива.Идея состоит в том, чтобы разбить массив на half .Если длина массива нечетная, это не совсем возможно, поэтому средний элемент помещается в левую или правую часть (это не имеет значения).

В этом случае он может разбить массивлибо в [9] и [82, 10], либо в [9, 82] и [10].Видимо, вы видели, как это происходит в последнем случае.

Только после расщепления фактические значения начинают играть роль.Это когда части объединены обратно.Сначала левая и правая части сортируются (рекурсивно), а затем левая и правая части объединяются.

Во время этого слияния сравниваются значение из левой части и значение из правой части.Каждый раз, когда меньший помещается в массив результатов, и «указатель», откуда он пришел, перемещается на одну позицию вперед.

Короче говоря: сортировка слиянием имеет две фазы: разбиение и слияние.Значения не сравниваются на этапе разделения, а только на этапе объединения.

Answer 2

Чтобы уточнить, сортировка или слияние не выполняются до тех пор, пока рекурсия не создаст два подмассива размера 1, с которых начинается слияние, а затем следует путь стека, сливающийся в шаблон глубины первый / левый первый (анимация создаетпохоже, что это параллельно).

Конкретная реализация, используемая в видео, работает с первым и последним индексами.Средний индекс фактически равен (первый + последний) / 2, и поскольку массив [4] = 9, массив [5] = 82, массив [6] = 10, первый = 4, последний = 6, средний = (4 + 6)) / 2 = 5, поэтому он разбивает подмассив на массив [4,5] и массив [6,6].Хотя это обычно для быстрой сортировки, большинство сортировок слиянием работают с начальным и конечным индексом, начальный индекс = первый индекс и конечный индекс = 1 + последний индекс.В этом случае begin = 4, end = 7, middle = (4 + 7) / 2 = 5, и разделение будет массив [4, 5) = массив [4,4] и массив [5,7} =массив [5,6] (используя ...} для указания конечного индекса = 1 + последний индекс).

Следует также отметить, что большинство библиотечных реализаций стабильных сортировок представляют собой разновидность итеративного слияния снизу вверхsort, который пропускает рекурсивный процесс и вместо этого рассматривает массив из n элементов как n отсортированных прогонов размера 1 и начинает слияние сразу, в порядке ширины (по массиву), объединяя четные и нечетные прогоны, что удваивает размер отсортированногоработает до тех пор, пока размер запуска> = размер массива.Типичными вариантами сортировки слиянием являются гибриды сортировки вставок и сортировки слиянием, такие как timsort.

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