Какова наихудшая сложность для сортировки ведер?

Чтобы объединить ведра, их сначала нужно отсортировать. Рассмотрим псевдокод, приведенный в статье Википедии:

function bucketSort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    nextSort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

nextSort(buckets[i]) сортирует каждое из отдельных ведер. Как правило, для сортировки ведер используется другой сорт (т. е. сортировка вставки), так как после того, как вы получаете вниз и размер, различные, нерекурсивные сортировки часто дают вам лучшую производительность.

Теперь рассмотрим случай, когда все элементы n оказываются в одном ведре. Если мы используем сортировку вставки для сортировки отдельных ведра, это может привести к худшему варианту производительности O(n^2). Я думаю, что ответ должен зависеть от того, какой вид вы выберете для сортировки отдельных ведер.

Если вы можете гарантировать, что каждая ячейка представляет собой уникальное значение (эквивалентные элементы), то наихудшая временная сложность будет O(m+n), как вы указали.

Сортировка по ведрам предполагает, что входные данные берутся из равномерного распределения. Это означает, что в каждое ведро попадает несколько предметов. В свою очередь, это приводит к хорошему среднему времени работы O(n). Действительно, если n элементов вставлены в каждое ведро так, что O(1) элементов попадают в каждое другое ведро (вставка требует O(1) на элемент), то сортировка ведра с помощью сортировки вставки требует в среднем также O(1) (это доказано почти во всех учебниках по алгоритмам). Так как вы должны за ведра, средняя сложность равна O (n).

Теперь предположим, что входные данные не получены из равномерного распределения. Как уже указывал @mfrankli, это может привести в худшем случае к ситуации, в которой все элементы попадают, например, все в первое ведро. В этом случае вставка сортировки потребует в худшем случае O (n^2).

Обратите внимание, что вы можете использовать следующий трюк для поддержания той же средней сложности O(n), обеспечивая при этом сложность O(N log n) в худшем случае. Вместо того чтобы использовать сортировку вставки, просто используйте алгоритм с O (N log n) сложностью в худшем случае: либо сортировка слиянием, либо сортировка кучи(но не быстрая сортировка, которая достигает O (n log n) только в среднем).

Это дополнительный ответ на @perreal. Я попытался опубликовать его в качестве комментария, но это слишком долго. @perreal правильно указывает, когда сортировка по ведрам имеет наибольший смысл. Различные ответы делают различные предположения о том, какие данные сортируются. Например, если сортируемые ключи являются строками, то диапазон возможных ключей будет слишком большим (больше, чем массив bucket), и нам придется использовать только первый символ строки для позиций bucket или какой-либо другой стратегии. Отдельные ведра должны быть отсортированы, потому что они содержат элементы с различными ключами, ведущими к O(n^2).

Но если мы сортируем данные, где ключи являются целыми числами в известном диапазоне, то ведра всегда уже отсортированы, потому что ключи в ведре равны, что приводит к линейной временной сортировке. Не только сортируются ведра, но сортировка стабильна , потому что мы можем извлекать элементы из массива ведер в том порядке, в котором они были добавлены.

То, что я хотел бы добавить, что если вы столкнулись с O (n^2) из-за природы ключей, подлежащих сортировке, сортировка по ведрам может быть неправильным подходом. Если у вас есть диапазон возможных ключей, пропорциональный размеру входных данных, то вы можете воспользоваться линейной сортировкой по временным интервалам, если каждый блок содержит только 1 значение ключа.