Сортировка массивов с Radixsort

Question

В настоящее время я пытаюсь понять Radixsort, и поэтому у меня есть короткий вопрос.

То, что я думаю, что это очень плохо, чтобы разобраться с RadixSort, это массив ниже:

"9999 ... 9, 9999 ... 9, 9999 ... 9"

Поскольку Radixsort будет сравнивать каждый номер первого, второго и третьего числа в массиве. Поэтому было бы лучше использовать другой сортировочный алгоритм для этого массива. Я прав или есть другие массивы, которые очень невыгодны для сортировки с Radixsort?

С наилучшими пожеланиями

Answer 1

Время Стоимость поразрядной сортировки есть O (нм), где п число элементов и т является сложность элементов. Вы правы, бывают случаи, когда это происходит не быстрее. При длинных целых строках m может превышать logn, который nlogn будет представлять собой временную стоимость сортировки слияния, например.