Разбираю различные алгоритмы сортировки. Один из простейших - сортировка подсчетом. Есть различные вариации. Я смотрел вhttp://ru.wikipedia.org/wiki/, на русской странице (на других языках могут попасться другие вариации).

Временная сложность алгоритма O(n+k). n - число элементов в массиве. k - длина отрезка, который вмещает элементы массива. k = maxEl - minEl + 1.

Опробуется алгоритм на массивах 4 видов:
1) Упоряд-й по возр-ю, k > n
2) Упоряд-й по убыв-ю, k > n
3) Случайные числа из "широкого" диапазона ("шире" диапазона индексов), k > n
4) Часто повторяющиеся случайные числа, k < n

Ниже привожу время работы:
- поиск min/max
- создание массива счетчиков
- подсчет
- формирование результ-го массива (запись эл-в по порядку)
- итоговое

В пункте подсчет массивы 1) и 2) обрабатываются быстрее, нежели 3) и 4)