Сортировки сравнениями не могут быть быстрее Ω(n log n) (см. свойства сортировок). Но граница относится к сравнению элементов. Если о ключах известно больше (они малые целые, у них есть цифры, они распределены равномерно), ключ можно использовать как индекс и сортировать за линейное время. Цена — ограничения на данные.
Сортировка подсчётом
Для целых 0..k: считаем, сколько раз встречается каждое значение, превращаем счётчики в префиксные суммы (count[v] становится числом элементов ≤ v) и раскладываем элементы в выходной массив. Если читать вход с конца, последний из равных значений попадает на последнее место, поэтому сортировка устойчива.
a = [4, 2, 2, 8, 3, 3, 1]
k = 8
count = [0] * (k + 1)
for x in a:
count[x] += 1
print("count :", count)
for v in range(1, k + 1):
count[v] += count[v - 1]
print("prefix:", count)count : [0, 1, 2, 2, 1, 0, 0, 0, 1]
prefix: [0, 1, 3, 5, 6, 6, 6, 6, 7]