Bucket sort - Algoritmy.net

Bucket sort

Bucket sort (bin sort) is a stable sorting algorithm based on partitioning the input array into several parts – so called buckets – and using some other sorting algorithm for the actual sorting of these subproblems.

Description

At first algorithm divides the input array into buckets. Each bucket contains some range of input elements (the elements should be uniformly distributed to ensure optimal division among buckets).In the second phase the bucket sort orderes each bucket using some other sorting algorithm, or by recursively calling itself – with bucket count equal to the range of values, bucket sort degenerates to counting sort. Finally the algorithm merges all the ordered buckets. Because every bucket contains different range of element values, bucket sort simply copies the elements of each bucket into the output array (concatenates the buckets).

The asymptotic complexity of bucket sort is , where is size of the input array, is the number of buckets and is the complexity of the inner sorting algorithm.

Usage

Bucket sort can be used for distributed sorting – each bucket can be ordered by a different thread or even by a different computer. Another use case is a sorting of huge input data, which cannot be loaded into the main memory by an ordinary algorithm. This problem can be solved by dividing the data into sufficiently small buckets, sorting them one by one by appropriate algorithm, while storing rest of the data in the external memory (e.g. hard drive).

Read full article from Bucket sort - Algoritmy.net