Elements are distributed among bins

Then, elements are sorted within each bin

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets. Under certain conditions for input data the bucket sort may run in linear time (Θ(n)). In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In computing, the term bucket can have several meanings. ... Pigeonhole sorting, also known as count sort, is a sorting algorithm that takes linear time (Θ(n)), which is the best possible performance for a sorting algorithm since one must inevitably look at each of the elements being sorted at least once, regardless of the sorting algorithm. ... A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ...

Bucket sort works as follows:

1. Set up an array of initially empty "buckets" the size of the range.
2. Go over the original array, putting each object in its bucket.
3. Sort each non-empty bucket.
4. Put elements from non-empty buckets back into the original array

Pseudocode

 function bucket-sort(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 next-sort(buckets[i]) return the concatenation of buckets[0], ..., buckets[n-1] 

Here array is the array to be sorted and n is the number of buckets to use. The function msbits(x,k) returns the k most significant bits of x (floor(x/2^(size(x)-k))); different functions can be used to translate the range of elements in array to n buckets, such as translating the letters A-Z to 0-25 or returning the first character (0-255) for sorting strings. The function next-sort is a sorting function; using bucket-sort itself as next-sort produces a relative of radix sort; in particular, the case n = 2 corresponds to quicksort (although potentially with poor pivot choices). Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ... A radix sort is a sorting algorithm that can rearrange integer representations based on the processing of individual digits in such a way that the integer representations are eventually in either ascending or descending order. ... Q sort redirects here. ...

Source Code for Bucket Sort in C

 //Vnm code support for linhcau and ngocut list sort(list s, typekey min, typekey max) { int i; typekey div, maxb[M], minb[M]; list head[M], t; struct rec aux; list Last; if (s == NULL) return(s); if (max == min) { for (Last = s; Last->next != NULL; Last = Last->next) ; return s; } div = ceil( (max - min) / M ); /* Find dividing factor */ for (i = 0; i < M; ++i) head[i] = NULL; /* Place records in buckets */ while (s != NULL) { i = (s->k - min) / div; if (i < 0) i = 0; else if (i >= M) i = M - 1; t = s; s = s->next; t->next = head[i]; if (head[i] == NULL) minb[i] = maxb[i] = t->k; head[i] = t; if (t->k > maxb[i]) maxb[i] = t->k; if (t->k < minb[i]) minb[i] = t->k; } /* sort iteratively */ t = &aux; for (i = 0; i < M; ++i) if (head[i] != NULL) { t->next = sort(head[i], minb[i], maxb[i]); t = Last; } return aux.next; } 

Postman's sort

The Postman's sort is a sorting algorithm, a variant of a bucket sort where attributes of the key are described so the algorithm can allocate buckets efficiently. This is the algorithm used by letter-sorting machines in the post office: first states, then post offices, then routes, etc. Since keys are not compared against each other, sorting time is O(cn), where c depends on the size of the key and number of buckets. This is similar to a radix sort that works "top down," or "most significant digit first."[1] In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Small-town post office and town hall in Lockhart, Alabama A post office is a facility (in most countries, a government one) where the public can purchase postage stamps for mailing correspondence or merchandise, and also drop off or pick up packages or other special-delivery items. ... A radix sort is a sorting algorithm that can rearrange integer representations based on the processing of individual digits in such a way that the integer representations are eventually in either ascending or descending order. ...

External links

• Bucket Sort in C++
• Bucket Sort Code for Ansi C
• Variant of Bucket Sort with Demo

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.4: Bucket sort, pp.174–177.
• Paul E. Black "Postman's Sort" from Dictionary of Algorithms and Data Structures at NIST.
• Robert Ramey The Postman's Sort C Users Journal Aug. 1992