Алгоритм сортировки слиянием выполняется в худшем случае O (n log n). Это один из самых простых алгоритмов с разумным временем работы. Это также прекрасный пример рекурсивного алгоритма.
Основная операция в этом алгоритме — объединение двух отсортированных списков. Базовый алгоритм слияния принимает два входа — «leftString» и «rightString», выходную строку «result» и три счетчика, которые изначально установлены в начале соответствующих массивов. Рекурсивные вызовы продолжают делить строку на части до тех пор, пока каждая часть не будет содержать только один элемент; очевидно, отсортирована строка из одного элемента. Затем алгоритмы объединяют эти маленькие части в более крупные отсортированные части, пока не получится одна отсортированная строка.
- Лучшее, среднее и наихудшее время выполнения: O(n log n)
- Сложность пространства: O(n)
Когда размер входных данных не слишком велик, сортировка вставками может быть более эффективной. Есть некоторые реализации, которые используют сортировку вставками до тех пор, пока не будет достигнуто некоторое пороговое значение, а затем они используют сортировку слиянием, комбинируя обе из них для достижения наилучших результатов.
Хотя сортировка слиянием является чрезвычайно эффективным алгоритмом по времени, у него есть один недостаток: шаг слияния требует вспомогательной строки. Это дополнительное хранилище и необходимое копирование записей являются недостатками.
