Bucket Sort

В отличие от counting sort (дискретные значения, один счётчик на каждое возможное значение) и radix sort (сортировка по разрядам), bucket sort работает с вещественными числами в известном диапазоне, например [0, 1). Диапазон делится на n равных интервалов ("корзин"): bucket[i] получает все значения из [i/n, (i+1)/n). Каждая корзина сортируется отдельно — обычно insertion sort (2.2.1.1), поскольку корзины при удачном распределении маленькие и константы важнее асимптотики. Затем корзины просто конкатенируются в порядке номеров — раз корзина i содержит только значения меньше значений корзины i+1, результат гарантированно отсортирован.Unlike counting sort (discrete values, one counter per possible value) and radix sort (sorting by digit), bucket sort works with real numbers in a known range, e.g. [0, 1). The range is split into n equal intervals ("buckets"): bucket[i] receives all values from [i/n, (i+1)/n). Each bucket is sorted separately — usually with insertion sort (2.2.1.1), since buckets are small under a good distribution and constants matter more than asymptotics. The buckets are then simply concatenated in index order — since bucket i only holds values smaller than bucket i+1's, the result is guaranteed sorted.

void bucket_sort(std::vector<double>& a) { // значения равномерно распределены в [0, 1)// values uniformly distributed in [0, 1)
    int n = a.size();
    std::vector<std::vector<double>> buckets(n);
    for (double x : a)
        buckets[int(x * n)].push_back(x); // прямое отображение значения в номер корзины// direct mapping from value to bucket index
    int idx = 0;
    for (auto& b : buckets) {
        std::sort(b.begin(), b.end());  // маленькая корзина: даже O(n log n) здесь дёшево// small bucket: even O(n log n) here is cheap
        for (double x : b) a[idx++] = x;
    }
}

n значений из [0, 1) раскладываются по n корзинам. Переключите распределение, чтобы увидеть разницу вживую: при равномерном входе в каждой корзине оказывается 0-2 элемента, при перекошенном — почти все значения падают в одну-две корзины, и bucket sort вырождается в обычную сортировку внутри них.n values from [0, 1) are distributed into n buckets. Toggle the distribution to see the difference live: with a uniform input, each bucket gets 0-2 elements; with a skewed one, almost all values fall into one or two buckets, and bucket sort degenerates into an ordinary sort inside them.

При равномерном распределении n значений по n корзинам в каждой корзине оказывается O(1) элементов в среднем — сортировка корзины тогда занимает O(1), суммарно O(n) на все корзины плюс O(n) на распределение = O(n). Но эта гарантия — вероятностная, а не структурная: она держится ровно постольку, поскольку распределение входа действительно равномерно. При сильно перекошенном распределении (например, степенном законе, где почти все значения близки друг к другу) почти все элементы попадают в одну корзину, и сортировка внутри неё деградирует до O(n log n) или O(n²) в зависимости от алгоритма — то есть весь выигрыш bucket sort исчезает, и он превращается в обычную сортировку сравнением с лишними накладными расходами на распределение.With a uniform distribution of n values into n buckets, each bucket ends up with O(1) elements on average — sorting a bucket then takes O(1), summing to O(n) across all buckets plus O(n) for distribution = O(n). But that guarantee is probabilistic, not structural: it holds exactly as long as the input distribution really is uniform. With a heavily skewed distribution (e.g. a power law, where almost all values cluster together) nearly all elements land in one bucket, and sorting within it degrades to O(n log n) or O(n²) depending on the algorithm — meaning bucket sort's entire advantage disappears, and it becomes an ordinary comparison sort with extra distribution overhead on top.