Слияние и рекурсия

Question

Итак, я просматривал код сортировки слиянием и увидел, что там используется рекурсия, я понял, что они используют «разделяй и властвуй», но я не могу понять, как все это происходит (т.е. как получается памятьвыделены и массивы разделены внутри). Было бы здорово, если бы кто-нибудь мог объяснить, как весь процесс происходит внутри стека с любым случайным адресом памяти (каждый бит, например, сколько памяти выделено функции и поток рекурсии), изображения очень помогли бы.

PS-Я много пытался получить информацию об этом в Google (искал "работа рекурсии в сортировке слиянием внутри стека" и многое другое) и попыталсяЯ сам это понял, но не смог. Заранее спасибо, что нашли время и помогли.

Answer 1

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

Типичная реализация topdown merge на самом деле не «разделяет» массив, а генерирует индексы, представляющие начало, середину и конец подмассива, и эффективно помещает эти индексы в стек при использовании рекурсии для вызова самого себя. Обратите внимание, что объединение не начинается до тех пор, пока не будут созданы два базовых случая размера подмассива == 1, затем выполняются объединение и разбиение, следуя цепочке вызовов вверх и вниз, сначала глубина, а затем слева сначала.

Для сравнениясортировка слиянием снизу вверх не использует никаких рекурсивных шагов и вместо этого начинает обрабатывать массив из n элементов как n подмассивов размера 1 и немедленно начинает слияние четных и нечетных подмассивов.

Затраты на сортировку слиянием сверху вниз не так уж и велики, поскольку рекурсия имеет временную сложность O (log (n)), тогда как сортировка слиянием сверху вниз и снизу вверх имеет временную сложность O (n log (n)). На этапах слияния, в конце концов, подмассивы становятся достаточно большими, чтобы большую часть времени проводить в идентичной функции слияния как для сортировки сверху вниз, так и для восходящей сортировки.