Ну, во-первых, нам нужно понять, как работает сортировка ведра:
- Создать пустой массив
- Переберите исходный массив и поместите каждый объект в корзину
- Сортировка каждого из непустых ведер
- Проверьте сегменты по порядку, а затем поместите все объекты обратно в исходный массив.
Это делает сортировку сегментов отличным алгоритмом для больших списков, которые необходимо отсортировать. Средняя сложность по времени составляет O (n + k), где n - количество ваших сегментов. Худшая временная сложность is (n ^ 2). Причина в том, что сортировка сегментов полезна, когда ввод равномерно распределен по диапазону, поскольку всякий раз, когда есть ключи, близкие друг к другу, они, вероятно, окажутся в одном и том же сегменте, в противном случае нам понадобится сегмент для каждого ключа в исходный массив.
В худшем случае сложность пространства равна O (nk).
Сложность пространства - это мера объема рабочей памяти, в которой нуждается алгоритм. Это означает, сколько памяти, в худшем случае, необходимо в любой точке алгоритма. Как и в отношении сложности времени, нас больше всего интересует, как растут потребности в пространстве, в больших терминах, с ростом размера N входной задачи.
Надеюсь, это помогло!