Сортировка вставками — достаточно простой алгоритм. Массив делится на 2 части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и включается в отсортированную. Имеет высокую вычислительную сложность O (nІ). Отсортировано начало массива A1, A2, …, Ai-1. Остаток массива Ai,…An не отсортирован. На очередном шаге Ai включается в отсортированную часть на соответствующее место. Пример такой сортировки — сортировка с помощью двоичного дерева.
Сортировка слиянием
Сортировка слиянием — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Блочная сортировка
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) —алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O (N) (на удачных входных данных).
Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента. В некоторых таких случаях для строк, возникающих в реализациях основанного на сортировке строк алгоритма сжатия BWT, оказывается, что быстрая сортировка строк в версии Седжвика значительно превосходит блочную сортировку скоростью.
