Структуры данных и модели вычислений
Сортировка "слиянием".
Этот метод является разновидностью метода "разделяй и властвуй"; впрочем, уместнее было бы назвать его "властвуй и объединяй".
Предположим, что у нас есть процедура СЛИВАЙ (, которая два уже отсортированных сегмента и
преобразует (сливает) в один сегмент , делая его полностью отсортированным. Тогда рекурсивная процедура
очевидно, сортирует сегмент , а для сортировки всего исходного массива достаточно выполнить оператор СОРТИРУЙ . Как видим, вопрос балансировки размера сегментов решается здесь просто. Число обращений к процедуре СЛИВАЙ
равно , а время ее выполнения легко сделать линейным от суммарной длины сливаемых сегментов.
Упражнения
- Разработайте процедуру СЛИВАЙ и вариант процедуры СОРТИРУЙ без использования рекурсии. Сколько дополнительной памяти требуется для ее реализации?
- Оцените теоретически время работы алгоритма по методу слияния.
- Напишите на известном вам алгоритмическом языке программу сортировки числового массива методом слияния и испытайте ее на массивах, сгенерированных с помощью датчика случайных чисел.
- Составьте таблицу, отражающую время работы вашей программы на массивах разной длины. Каков максимальный размер массива, который можно отсортировать составленной программой на вашем компьютере?
