Сортировка сегментов может иметь различное количество сегментов в зависимости от того, как вы хотите сбалансировать пространство и сложность времени.Если в этом случае вы используете 10 или более блоков, и каждый ключ имеет свой собственный блок, время выполнения для элементов n и N блоков будет равно O (n + N).В противном случае время выполнения будет зависеть от алгоритма сортировки, используемого в каждом сегменте, поскольку могут быть сегменты с несколькими элементами.
Алгоритм предполагает, что с каждым элементом уже связан ключ, поэтому, если я понимаю, что вы спрашиваетевам нужно будет «получить состав ключа» один раз для каждого элемента, когда вы помещаете их в сегменты, а также когда вы выводите отсортированный список.
Наконец, вам не обязательно проверять, пусто ли полев зависимости от того, как ваш алгоритм обрабатывает сортировку каждого отдельного сегмента.Для элемента [k, e] , где k - ключ, а e - элемент, он будет помещен в корзину k .или нет, это ведро пусто.Ваш алгоритм может поддерживать отсортированный список для каждого сегмента или сортировать все сегменты до того, как он выведет окончательный отсортированный список.Это может повлиять на количество проверок на пустоту.Наконец, когда алгоритм выводит отсортированный список, он пропускает пустые сегменты, поэтому для этого может потребоваться проверка на пустоту каждый раз.