Сортировка слиянием :: Merge sort
Эффективный алгоритм сортировки предложенный легендарным Джоном фон Нейманом в 1945 году.
Сортировка была придумана во время работы над "Манхеттенским проектом" как средство обработки больших массивов статистических данных.
Алгоритм
Разделение: массив разбивается на два подмассива.
Упорядочивание: подмассивы сортируются (к ним рекурсивно применяется сортировка слиянием).
Слияние: упорядоченные подмассивы объединяются в один отсортированный массив.
Характеристики алгоритма
| Название | Сортировка слиянием (Merge sort) |
|---|
| Автор | Джон фон Нейман |
|---|
| Год | 1945 |
|---|
| Класс | Сортировки слиянием |
|---|
| Устойчивость | Да |
|---|
| Сравнения | Да |
|---|
| Сложность по времени | Худшая | O(n log n) |
|---|
| Средняя | O(n log n) |
|---|
| Лучшая | O(n log n) |
|---|
| Сложность по памяти | Общая | O(n) |
|---|
| Дополнительная | O(n) |
|---|
Ссылки
Сортировка слиянием
Merge sort
Реализация на различных ЯП
Джон фон Нейман
