3622
правки
Изменения
м
→Итеративный алгоритм
===Итеративный алгоритм===
[[Файл:Merge sort itearative.png|300px|right|thumb|Пример работы итеративного алгоритма сортировки слиянием]]
При итеративном алгоритме не происходит рекурсивного запуска, что сохранит используется на <tex>O(\log n)</tex> меньше памяти, которое отдавалось для стека вызововкоторая раньше тратилась на рекурсивные вызовы.
<code style="display: inline-block">
'''function''' mergeSortIterative(a : '''int[n]'''):
merge(a, j, j + i, min(j + 2 * i, n))
</code>
==Время работы==
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
