оценки
не требует дополнительной памяти, алгоритм неустойчив, поведение неестественное
► общее быстродействие О(nlog(n))
► теоретически возможен (но редко) 
О(n^2)
– худший случай
►для сортировки больших и неупорядоченных массивов
Сортировка подсчетом
23 11 4 56 9
35 7
СЧЕТЧИКИ |
4 |
3 0 |
0 |
6 0 2 0 5 |
1 |
0 |
4 |
7 |
9 |
11 |
23 |
35 |
56 |
►B = <20, -5, 10, 8, 7> ►S = < 4, 0, 3, 2, 1> ►B’= <-5, 7, 8, 10, 20>
Оценка
►требуются два дополнительных массива для размещения результирующей последовательности и временного
массива для счетчиков
►Трудоемкость алгоритма –n2/2
4.3. КВАДРАТИЧНАЯ ВЫБОРКА |
|||||
23 |
11 |
4 |
56 |
9 |
|
35 |
7 |
- 2 |
|
|
sqrt(n) -3 |
n’ |
|
|
|
||
23 |
11 |
4 |
56 |
9 |
35 |
7 |
23 |
11 |
0 |
56 |
9 |
35 |
0 |
|
|
1000 |
|
|
|
1000 |
23 0 |
1000 |
56 |
0 |
35 |
0 |
|
0 |
|
1000 |
||||
|
1000 |
|
|
1000 |
|
|
Оценка
►уменьшает число сравнений
►но требует дополнительного объема памяти
►Общее число сравнений для случая 
точного квадрата равно 2n*sqrt(n)
► необходимый резерв памяти – поле 
длиной элемент n+sqrt(n)
A 6. Сортировка слиянием |
||||||||
5 |
6 |
3 |
1 |
8 |
3 |
1 |
4 |
1 |
B |
|
|
0 |
|
2 |
4 |
|
5 |
3 |
6 |
5 |
8 |
1 |
3 |
4 |
1 |
1 |
|
|
6 |
|
0 |
2 |
|
4 |
5 |
6 |
5 |
|
8 |
1 |
3 |
4 |
1 |
1 |
6 |
6 |
|
8 |
0 |
2 |
1 |
4 |
5 |
5 |
|
1 |
3 |
1 |
|
|||
5 |
6 |
|
8 |
0 |
2 |
4 |
5 |
|
|
|
1 |
3 |
1 |
1 |
|
||
6 |
|
|
|
0 |
2 |
4 |
5 |
|
6.1. ОДНОКРАТНОЕ СЛИЯНИЕ
Анализ
O(nlog2n)
Требуется память дополнительная
для сортировки данных на устройствах последовательного доступа - сортировка 
файлов
эффективно для больших N