Двусторонняя сортировка слиянием и сортировка слиянием - PullRequest
Новая
       17

Двусторонняя сортировка слиянием и сортировка слиянием

2 голосов
/ 21 июня 2019

Чем двухсторонняя сортировка слиянием рекурсивно отличается от сортировки слиянием?

Предположим, есть 5 номеров для сортировки 8,9,1,6,4 В Merge Sort мы делим вот так Шаг 1: {8,9,1} {6,4}

Шаг 2: {8,9} {1} {6} {4}

Шаг 3: {8} {9} {1} {6} {4}

Теперь объединить

Шаг 4: {8,9} {1} {4,6}

Шаг 5: {1,8,9} {4,6}

Шаг 6: {1,4,6,8,9}

Но с помощью двухсторонней сортировки мы разделяем массив на 2 элемента каждый (но согласно википедии, перед объединением необходимо отсортировать каждые 2 элемента. https://en.wikipedia.org/wiki/K-way_merge_algorithm) Итак, он также начинается с одного элемента и объединить их право? Итак, шаги для массива: 8,9,1,6,4

Step1: {8,9} {1,6} {4} [это нечетное слияние элементов в конце]

Шаг 2: {1,6,8,9}. {4}

Шаг 3: {1,4,6,8,9}

Итак, количество шагов здесь уменьшается. Тогда какой будет алгоритм для этого? Является ли двусторонняя сортировка слиянием слиянием более эффективной, чем сортировка слиянием?

1 Ответ

2 голосов
/ 21 июня 2019

Является ли двухсторонняя сортировка слиянием слиянием более эффективной, чем сортировка слиянием?

Другое имя для итеративной двухсторонней сортировки слиянием - восходящая сортировка снизу вверх, тогда как другое имя для рекурсивнойсортировка слиянием - сортировка слиянием сверху вниз.

Как правило, оптимизированная сортировка слиянием снизу вверх несколько эффективнее, чем оптимизированная сортировка слиянием сверху вниз.Сортировка сверху вниз выполняет операции стека O (n) над индексами, сгенерированными рекурсивным «разбиением» массива.Если n не является степенью 2, то сортировка слиянием снизу вверх делает больше сравнения и перемещений, но это меньше, чем накладные расходы на операции стека сортировки слиянием.Для больших массивов разница составляет менее 5%.

Для гибридной сортировки вставок / слияний, в которой используется сортировка вставок для n / m групп m элементов, сортировка слиянием снизу вверх может регулировать m , чтобы иметь значение n, не являющееся степенью 2.

Сортировка сверху вниз предназначена в основном для обучения.Несмотря на небольшую разницу в производительности и стековом пространстве, большинство библиотек используют некоторую разновидность сортировки по принципу «снизу вверх» для стабильной сортировки.

...