если у нас есть n элементов с ключами: {0,1, -1} и мы хотим их отсортировать, сколько сравнений у нас, по крайней мере, в худшем случае?
Вот решение, которое работает в O (n):
Для каждой записи ключа / значения выполните
lists[entry.key + 1].append(entry)
Объединить три списка в один длинный список.
Таким образом, у вас нет сравнения между ключами.
При небольшом фиксированном числе возможных значений вы можете сортировать по линейному времени что-то вроде , считая сортировку .
Это зависит от используемого алгоритма и распределения элементов.