Bucket Sort
This page gives a brief introduction to bucket sort.
Definition
Bucket sort is a sorting algorithm that works well when the data to be sorted has a large value range but is fairly uniformly distributed.
Procedure
Bucket sort proceeds in the following steps:
- Set up a fixed number of arrays to serve as empty buckets;
- Go through the sequence and put the elements one by one into their buckets;
- Sort every non-empty bucket;
- Put the elements from the non-empty buckets back into the original sequence.
Properties
Stability
If the inner sort is stable and inserting the elements into the buckets does not change their relative order, then bucket sort is a stable sorting algorithm.
Each block holds only a few elements, so insertion sort is the usual choice. Bucket sort is then a stable sorting algorithm.
Time complexity
Let \(n\) be the number of elements and \(k\) the number of buckets. If the elements fall into the buckets independently and uniformly, the average-case time complexity of bucket sort is \(O(n + n^2/k + k)\) (splitting the value range evenly into \(k\) blocks + sorting + merging the elements back together), which is \(O(n)\) when \(k\approx n\).1
The worst-case time complexity of bucket sort is \(O(n^2+k)\).
Implementation
Below, a[] is indexed from \(1\), and we require \(0\le a_i\le w\) and \(0\le n<N\), where \(w\) is an upper bound on the largest key.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | |
References and notes
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: partychicken, 24OI-bot, ouuan, NachtgeistW, Enter-tainer, Marcythm, iamtwz, Xeonacid, Menci, shawlleyw, Tiphereth-A, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.