Я только что прочитал страницу Википедии оСортировка ковшей, В этой статье говорится, что сложность наихудшего случая - O (n²). Но я думал, что сложность в худшем случае была O (n + k), где k - количество сегментов. Вот как я вычисляю эту сложность:

Добавьте элемент в корзину. Используя связанный список, это O (1)Проходя по списку и помещая элементы в правильное ведро = O (n)Слияние ведер = O (k)O (1) * O (n) + O (k) = O (n + k)

Я что-то пропустил?