2. Естественное двухпутевое слияние

Длина фрагментов на начальном этапе не 1, а выбирается из соображений естественной упорядоченности элементов.

Выбираются фрагменты: (19) (10 35) (14 20) (18 28) (12)

(12 19) (10 18 28 35) (14 20)

(12 14 19 20) (10 18 28 35)

( 10 12 14 18 19 20 28 35 )

11. Методы сортировки подсчётом

Сортировка подсчётом сравнений.

Все ключи попарно сравниваются. Считается максимальным ключ, где больше всего сравнений в его пользу. Минимальным — максимальное количество раз был меньше.

Пример:

5 17 10 7 3 13

Массив счётчиков A: 1 1 1 1 1 1

2 6 4 3 1 5

3 5 7 10 13 17

Число сравнений: n^2/2

1. Пирамидальная сортировка

Состоит из 2-х этапов:

1. массив преобразуется в пирамиду (дерево).

1 2 3 4 5 6 7

15 17 20 38 32 18 27

В массиве дети: 2i и 2i+1

15

17 20

38 32 18 27

Проверяем выполнение условия «каждый родитель больше детей». Начинаем с середины.

20 > 18 и 27 ? Нет. Наибольший меняется местами с родителем: 15 17 27 38 32 18 20

Выбираем элемент слева:

17 > 38 и 32 ? Нет: 15 38 27 17 32 18 20.

15 > 38 и 27 ? Нет: 38 15 27 17 32 18 20.

15 > 17 и 32 ? Нет: 38 32 27 17 15 18 20.

1 этап закончен.

2. из пирамиды построить упорядоченный массив.

Берётся первый узел (38), извлекается, на его место ставится старший из детей (32), снова извлекается и т.д.:

38 32 17 27 x 15 18 20

32 27 17 20 x 15 17 x

27 20 17 18 x 15 x x

20 18 17 x x 15 x x

18 17 15 x x x x x

17 15 x x x x x x

15 x x x x x x x x

Трудоёмкость: O(N*log(N,2))

2. Сортировка убывающими вставками. Метод Шелла

Если 16 элементов. Сначала разбивается на 8 групп по 2 элемента (с шагом 8, например 1 и 9 элемент), устанавливается порядок, затем группы по 4 элемента (с шагом 4), снова устанавливается порядок. Число элементов в группе удваивается, шаг уменьшается вдвое. В последний раз будет 2 группы, с чётными и нечётными номерами. В последний раз рассматривается весь массив как одна группа.

Пример:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

47 35 44 17 23 33 41 10 | 14 20 22 30 5 12 16 7

14 20 22 17 5 12 16 7 47 35 44 30 23 33 41 10

H = H/2

14 20 22 17 | 5 12 16 7 | 47 35 44 30 | 23 33 41 10

5 12 | 16 7 | 14 20 | 22 10 | 23 33 | 41 17 | 47 35 | 44 30

5 7 14 10 16 22 17 23 20 7 30 44 33 47 35

5 7 10 12 14 16 17 20 22 23 30 33 35 41 44 47

Сравнений: N^3/2 / 2

3. Метод Хоара

Случайно выбирается «средний» элемент. Слева от него все меньше, справа — больше. Если это не выполнено, элементы переставляются. Движутся слева. Если элемент не на своём месте, его позиция запоминается. Начинается проход справа. Как только находится второй элемент не на своём месте, происходит перестановка.

Пример:

11 3 7 9 12 4 18 8 14

Возьмём первый элемент в качестве среднего.

I → ←J

(11) 3 7 9 12 4 18 8 14

I = 12

J = 8

8 3 7 9 x 4 18 12 14

8 3 7 9 4 (11) 18 12 14

8 _ 3 7 9 4 |

9 3 7 4 8 |

Трудоёмкость N*log(N,2)

4. Поразрядная обменная сортировка

2 1 6 7 5 3 4 0

010 001 110 111 101 011 100 000

i → ← j

010 001 110 111 101 011 100000 (подчёркнутые не в своих половинах)

010 001 000 111 101011 100 110

010 001 000 011 101111 100 110

Теперь по второму разряду:

010 001 000 011 | 101111 100 110

010 001 000011 | 101111 100 110

000 001 010 011 | 101111 100 110

000 001 010 011 | 101100111 110

Теперь по правому

т

000 001010011 | 101100111 110

000 010 001 011 | 101100111110

000 001 010 011 100 101 110 111

Трудоёмкость: N*log(N,2)