Почему мы делим массивы до одного элемента в сортировке слияния

Я читаю алгоритм сортировки слиянием. У меня вопросПочему мы делим массивы до одного элемента в сортировке слияния

Предположим, что мы имеем список Следующий список

= 5 4 1 3 6 8 9 7

Первый список делят на 4 -4 элементов. Мы называем левой и список с правой стороны

5 4 1 3 and 6 8 9 7

Затем разделите 5 4 1 3 на следующие

5 4 and 1 3

Затем разделите 5 и 4 в

5 4

При сортировке мы начнем сортировку от последний шаг и переход до этапа 1 (где у нас есть 4-4 элемента)

Вопрос: В любом случае, когда мы делим список до 1-1, и мы сортируем и объединяем список в каждый момент, то почему бы не разделить список только на 4-4 элемента. Потому что и в этом случае мы будем делать слияние списка. Зачем перебирать до 1-1 элемент

источник

2016-05-31 Nitesh

_base case_ возникает, когда текущая итерация имеет один или два элемента. Когда это произойдет, алгоритм либо вернет один элемент, либо отсортирует два элемента на месте. Это предполагает, что вы работаете с рекурсивной реализацией mergesort, которая, как я полагаю, вы есть. –

Поскольку массив только одного элемента уже отсортирован. – Shravan40

Чтобы прояснить комментарий Тима Бигелейзена, восходящая/итеративная реализация сортировки слияния пропускает все рекурсивное расщепление массива и начинается с предположения, что массив размером N является N подмассивами размера 1. Большинство реализаций реализаций слияния есть некоторые варианты сортировки слияния снизу вверх, такие как [timsort] (http://en.wikipedia.org/wiki/Timsort). – rcgldr

1-элементный список сортируется естественно. Мы объединяем два отсортированных списка по 1 элементу, чтобы получить отсортированный список из 2 элементов, затем сгруппируйте отсортированные списки из 2 элементов, чтобы отсортировать список из 4 элементов и так далее.

процедура Merge предназначена для отсортированных списков, поэтому мы не можем применить слияние с несортированными 5 4 1 3 и 6 8 9 7 списков

источник

2016-05-31 10:53:36 MBo

Хорошо. благодаря – Nitesh

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

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

источник

2016-05-31 10:55:12 Glubus

Теоретически это потому, что процедура слияния должна принимать два отсортированных списка. 4-элементный список не сортируется, а список из одного элемента.

На практике мы не разбиваем списки на один элемент. Поскольку сортировка слияния не является наиболее эффективным алгоритмом сортировки для небольших списков, сортировка вставки. Таким образом, общая оптимизация заключается в использовании сортировки вставки для сортировки небольших списков и объединения их с сортировкой слияния.

источник

2016-05-31 11:06:43

Почему мы делим массивы до одного элемента в сортировке слияния

ответ

Смежные вопросы