Сортировка слиянием (merge sort)

1.

Сортировка слиянием
(merge sort)
ИВТб 1303 подгруппа 2
20.12.2023

2.

Определение
Сортировка слиянием алгоритм сортировки, который упорядочивает списки (или
др. структуры данных, доступ к элементам которых можно
получать только последовательно) в определённом
порядке.
Эта сортировка — хороший пример использования
принципа «разделяй и властвуй».

3.

Пример реализации алгоритма
сортировки слиянием на ЯП С

4.

5.

Схема алгоритма сортировки
слиянием

6.

Характеристики сортировки
слиянием
Детерминированность
Сложность
Память
Лучший случай: O(n log n)
Средний случай: O(n log n)
Худший случай: O(n log n)
(n — количество сортируемых
элементов)
Использует дополнительную
память размером
сортируемого массива, что
делает ее неэффективной
для больших наборов
данных.
Скорость
Сортировка слиянием — одна из
быстрых сортировок, физически
невозможно создать более быстрый
алгоритм, хотя сортировка слиянием не
единственная с такой скоростью
Сортировка слиянием
является
детерминированной - для
одинаковых входных данных
она всегда будет давать
одинаковый результат.
Устойчивость
Сортировка слиянием является
устойчивой - элементы с одинаковым
значением будут упорядочены в том же
порядке, в котором они находятся в
исходном массиве.