Алгоритм метода сортировки, использующий слияние двух упорядоченных частей массива.

Будем сортировать массив из 13 элементов, но для работы этого метода нужно добавить количество элементов до два в степени к. Мы добавляем до 16 элементов.

Рис. 14

Для работы алгоритма необходимо дополнить количество элементов в массиве так, чтобы N=2^x.

Рис. 15

Время выполнения данного алгоритма стабильно и стремится к Q(N)=N*log₂N.

Плюсы:

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

Минусы:

• при большом количестве данных программа может обращаться к внешней памяти, что ведет к потере скорости;
• при копировании массивов идет потеря скорости и памяти;
• при сортировке слишком большого массива могут возникнуть проблемы с составлением вспомогательного массива С.
• требует добавления элементов до 2ⁿ

Рекомендаци

Рекомендуем использовать метод совместно с методом вставки. т.к в некоторых случаях нерационально дополнять массив до степени двойки. Разрыв между степенью двойки увеличивается с каждым разом.(между степенью двойки и следующей степенью двойки: 512…1024)поэтому выгодно брать самое близкую степень двойки после сортировки этим методом использовать метод вставки для улучшения эффективности данного алгоритма.

Массив из 568 элементов

Берем 512 элементов и сортируем по данному методу. После окончания сортировки сортируем этот же массив методом вставки.

Дата добавления: 2015-11-30