Our Discord: https://discord.gg/ajezQHdnRU. Please email mathteca@gmail.com if any organization or society wants to partner with Mathteca.
Bucket sort is a sorting algorithm that is suitable for situations where the value range of the data to be sorted is large but the distribution is relatively uniform.
Bucket sort proceeds as follows:
Set a quantitative array as an empty bucket;
Traverse the sequence and put the elements into the corresponding buckets one by one;
Sort each bucket that is not empty;
Put the elements from the non-empty bucket back into the original sequence.
Bucket sort is a stable sorting algorithm if a stable inner sort is used and the relative order of elements is not changed when elements are inserted into the bucket.
Since there are not many elements in each block, insertion sort is generally used. Bucket sorting is a stable sorting algorithm at this time.
The average time complexity of bucket sort is O(n + n^2/k + k) (divide the range into n chunks + sort + recombine elements), which is O(n) when k is approximately equal to n.
The worst time complexity of bucket sort is O(n^2).