Сортировка слиянием :: Merge sort

Джон фон Нейман
Эффективный алгоритм сортировки предложенный легендарным Джоном фон Нейманом в 1945 году.

Сортировка была придумана во время работы над «Манхеттенским проектом» как средство обработки больших массивов статистических данных.

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

Алгоритм

Разделение: массив разбивается на два подмассива.
Упорядочивание: подмассивы сортируются (к ним рекурсивно применяется сортировка слиянием).
Слияние: упорядоченные подмассивы объединяются в один отсортированный массив.

Характеристики алгоритма

Название Сортировка слиянием (Merge sort)
Автор Джон фон Нейман
Год 1945
Класс Сортировки слиянием
Устойчивость Да
Сравнения Да
Сложность по времени Худшая O(n log n)
Средняя O(n log n)
Лучшая O(n log n)
Сложность по памяти Общая O(n)
Дополнительная O(n)

Ссылки

Сортировка слиянием в Википедии
Merge sort on Wikipedia
Реализация на различных ЯП
Джон фон Нейман в Википедии

Добавить комментарий