Talk:Bucket sort

n=number of elements and also n=number of buckets

"The most common variant of bucket sort operates on a list of n numeric inputs between zero and some maximum value M and divides the value range into n buckets each of size M/n" is a bit misleading IMO. Could the number of buckets be changed to b, so that n=number of elements matches the other sort pages? Neodymion (talk) 03:24, 22 June 2008 (UTC)

I agree. And it's not just misleading but plain wrong. As the number of inputs appear not to be referenced later, I'm removing the letter n for the number of inputs at this moment. 'b' would be a better choice for the number of buckets in my opinion, but the significant book by Cormen et. al. uses 'n'. 129.241.157.9 (talk) 02:28, 6 October 2008 (UTC)

The algorithm given is not linear-time

The article currently says:

Bucket sort runs in linear time ... It 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.

Correct me if I'm wrong, but because of the recursion in step 3, this algorithm is not O(n) as given. It is O(kn) where k is the recursion depth. --Doradus 07:12, Apr 30, 2005 (UTC)

If k is determined at implementation, then it is a constant at run time and is ignored, leaving O(n).

If k is determined at runtime as a function of n, then we have O(f(n)*n) which, if f(n) is linear, reduces back to O(n).

If k is determined at runtime by a property of the data (not the amount of data), then things get tricky. For example, if you were doing a base-10 radix sort, then you would have O(f(n)*n) where f(n) is log-base10(max(n)).

That's how I understand it.

--Flatline 15:52, 2005 Apr 30 (UTC)

Your treatment of the second case is wrong. If f(n) is linear in n, then O(f(n)*n) = O(n²). Aragorn2 13:28, 21 March 2006 (UTC)

Linear Time is both Possible and Expected from Bucket Sort:

I believe the condition required to cause bucket sort to be maximally bounded (see big-O notation) by O(n) is the uniform distribution of the inputs across the range of possible inputs. Each bucket is "expected" (see statistics: expected value) to contain [range]/[number of buckets] elements. Thus, if a reasonable sort (such as counting sort or an embedded bucket sort) is applied to each bucket, the total sorting of all buckets will, in an average case, be maximally bounded by O(n). However, as has been pointed out, the worst-case bucket-sort can explode into just as poor of a running time as any other sorting algorithm. Bucket sorting is considered linear, because the average-case is linear given certain conditions.

--Dinre (talk) 17:57, 14 February 2008 (UTC)

I think you are right in this, but isn't it so that O(kn) is also O(n) when k is not n? When k is of siginicant size it will change the lineairity (don't know if that is proper English) of the algorithm.

Another flaw I think in the article is step 3: Sort each non-empty bucket. Isn't this what this algorithm is supposed to do? As I see it:

1. Set up an array with initially empty buckets called B. You need to have a size of this bucket, which is usually represented as an array. To find a size you can walk through the set S of items that need to be sorted and seek the maximum sort-key k. This will take n operations, where n is the number of items in S;
2. Go through S and put every item in the bucket that corresponds with the sort-key k.
3. B now contains buckets that are either empty as non-empty, filled with an item;
4. One can now put all the items from B back into S, being sorted.

I think this is a more correct version, but that's how I understand this algorithm. --wackmaniac 00:47, 2005 Nov 30 (CET)

okay after reading the above comments here is how bucket sort works

---

1. Let A be the i/p array and let B be the o/p array having same size as i/p array

   Note:array B is more like a setinel. ie imagine each element of B to point to a bucket, that is a link list.

2. Based on a sort key,eg let this be the MSD of digits the i/p array A , place elements of A in B.

  eg A{57,15,32,50,11,99,45,30,62,91} , then B{X,[15->11],X,[32->30],X,[57->50],[62],X,X,[99->91]}

3. Now sort the buckets individually in B based on the fav algo of your choice.

  eg B{X,[11->15],X,[32->30],X,[50->57],[62],X,X,[91->99]}

4. Concat the results of B

  eg [11->15]->[32->30]->[50->57]->[91->99]

Note: -> indicates a pointer by suneel, iit chicago

Rewrite

"Bucket sort runs in linear time (Θ(n)) when input is drawn from a uniform distribution."

I have no idea, what the author wants to tell me, but I get the distinct impression that I should rewrite this article.

"partitioning an array into a finite number of buckets and then sorting each bucket"

Oh my god. Rewrite from scratch I think...

Ah, I see now. There is no consesus which algorithm is called bucket sort. I am still searching for the original source of the name bucket sort to clear it up, but for now I have not found anything.

Source Code

While an example of an algorithm in source form is not a bad thing, in general pseudocode is preferable for a number of reasons. Wikipedia is not s source code repository, and once sample implementations start getting added people feel inclined to add more in their favourite language of choice. This ends up swamping articles on algorithms with an inordinate amount of source code that usually adds nothing not already provided by the pseudocode example. The best place for example implementations is something like Literate Programs which has a wiki specifically designed to hold documented source code in a wide variety of languages. Please note there are potential licensing issues involved as Wikipedia is GFDL while LP is not (though still an open license). Leland McInnes 06:35, 6 April 2006 (UTC)

Wrong algorithmic order?

Bucket sort is worst case O(n lg m) where m is the number of distinct possible elements. If m > number of buckets, then (as the article says) it must be recursively applied to the buckets. The recursion depth is O(lg m). COnsider sorting 16 bit ints. You can bucket sort with 256 buckets, applied twice. 24 bit ints will require 3 applications, 32 bit, 4 and so on.

Esentially, the number of passes (recursion depth) is linear in the key length, or logarithmic in the number of distinct keys. Serviscope Minor 01:56, 21 November 2006 (UTC)

More Abstractly

My understanding is that Bucket or Bin sort is a class of sorting algorithms that is identified by the use of buckets or bins in the initial pass over the elements to be sorted. If your elements are evenly distributed and you know enough about the keys you can reduce the asymptotic running time by selecting an appropriate number of bins. This is how O(n log n) can be reduced to O(n). Beware! If you do not have an even distribution a large number of elements in a single bin will erase any benefits and you will have the added cost of the first run as well as any space and copy costs you accrued in your implementation. —The preceding unsigned comment was added by 24.198.83.109 (talk) 02:19, 26 April 2007 (UTC).

Mess

The articles bucket sort, pigeonhole sort, Counting sort, Tally sort and to some extent, radix sort constitute a mess due to the similarity (if not sameness in terms of the masic smart trick) of the algorithms. I learned Knuth & stuff like 30 years ago, so I am not of fresh memory, but IMO "bucket" and "pigeonhole" are synonyms. I cleased some carelless texts in a couple of places, but Expert attention is needed. `'Miikka 01:59, 4 July 2007 (UTC)

I agree. Possibly the whole set of articles needs editing based on hash table collision handling methods (linear, quadratic, chained and tree). A much faster sort than with quicksort for data with randomised keys within a range can be implemented using a linear hash algorithm, but the table (set of buckets) needs to be sized as for a hash table. Copsewood (talk) 14:22, 17 October 2009 (UTC)

Memory Requirements

The article should mention the amount of memory the sort requires. (Some of the other sort articles do.) —Preceding unsigned comment added by 206.53.197.12 (talk) 01:02, 27 October 2007 (UTC)

Implementation link

I got this when ran implementation in C++:

Program received signal SIGSEGV, Segmentation fault.

Yeah, that is a common effect of using C and C++, I know, I know. I've had such in Java too. ... said: Rursus (^mbork³) 16:17, 17 November 2009 (UTC)

implementation doubts

I don't understand this fully:

list sort(list s, typekey min, typekey max)
{
       int i;
       typekey div, maxb[M], minb[M];
       list head[M], t;
       struct rec aux;

       if (s == NULL)
               return(s); 
       if (max == min)
               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]);
                       for( ; t -> next != NULL; t = t->next )
                               ;
               }
       return aux.next;
}

What are: list, aux, typekey? I can see that aux is a structure, bur what are its basic elements? and I don't think this will run in TC as is (or with minor modifications) --Sylvestersteele (talk) 17:28, 29 April 2008 (UTC)

proof of linearity

Can someone put up a proof of linearity for bucket sort? I think that'll be very helpful. Expert needed --Sylvestersteele (talk) 17:30, 29 April 2008 (UTC)

The proof is pretty simple: it's linear on average if you use M/n buckets and the elements are uniformly distributed, because a constant number of elements end up in each bucket. But I'm not a valid source, so it'd be nice to find a book or paper or something on this. Dcoetzee 06:38, 6 October 2008 (UTC)

-- A proof can be found in: Probability and Computing By Michael Mitzenmacher, Eli Upfal, Chapter 5.2.2 (see http://books.google.com/books?id=0bAYl6d7hvkC ) —Preceding unsigned comment added by 130.149.12.68 (talk) 16:00, 26 November 2008 (UTC)

-- Is impossible that the algorithm can be O(n), It has a worst case n^2 when all elements fit in the same bucket. Worse yet in such a case the algorithm would loop forever. Let's put for example that all elements are equal. Then according to the description all would fit in the same bucket. Now what happens if you apply it recursively? All will fit again in the same bucket again and again. . .

Ok maybe that could be fixed if tested for such degraded case. But then things do not start too look so good then. At most would be O(nlogn) on average since is basically sort of quicksort upside-down and then quicksort is nlogn on average with a worst case O(n^2) too. —Preceding unsigned comment added by Waldoalvarez00 (talk • contribs) 19:20, 25 October 2008 (UTC)

Yes, I think you're right. The core of the problem is: how large must the buckets be, and how much complexity will handling the buckets need? I would just, between the thumb and the index finger guess O(log(n)), but one can design cases, sets of arrayed sortable elements, where the bucket size needed is 1. On the average of cases, however, the buckets might need to be larger. ... said: Rursus (^mbork³) 16:26, 17 November 2009 (UTC)

The book "Probability and Computing By Michael Mitzenmacher" mentioned by sir 130.149.12.68, only claims that bucket sort has a lower sorting time in certain cases, such as when the input data set already has a known distribution, which according to my thinking is the same as "it is already inherently sorted". Of course! One can get very good sorting metrics even from bubblesort, provided the sorting array is already perfectly sorted and the local version of bubblesort doesn't garble it. ... said: Rursus (^mbork³) 16:39, 17 November 2009 (UTC)

Bucket sort has O(n) worst case running time if the input is uniformly distributed, as already stated several times on this discussion page (and perhaps very clear in the introduction of a previous revision of this article). And Rursus, you get it wrong - "it is already inherently sorted" is not the same as knowing the distribution. For example you know the (probability) distribution of the numbers rolling a fair dice several times. It is uniform as well. But they are not sorted (and you don't know the exact outcome a priori). The proof of the O(n) worst case bound is not complicated. A good explanation of the algorithm and the proof is in: Cormen et. al.: Introduction to Algorithms. 2nd. MIT Press, 2001, ISBN 0-262-03293-7, page 174

--Gms (talk) 22:30, 11 June 2010 (UTC)

Worst-case complexity?

The info-box currently says that the worst-case complexity is O(n^2), but the article doesn't discuss this at all. So where does this come from? Oli Filth^{(talk|contribs)} 23:19, 31 August 2011 (UTC)

Stable?

There's no information in the article on if it's stable, I did Control-F for "stable" and found that this article is classified under "Stable sorts", but relevant information should be in the article. Also, I was looking online, and apparently it's stableness relies on the stableness of the sort that is used to sort the bins. — Preceding unsigned comment added by 70.131.44.130 (talk) 03:55, 13 February 2019 (UTC)

Out-of-bounds in pseudocode

The pseudocode given in the article will always result in an out-of-bounds error for zero-indexed arrays, as the expression floor(k × array[i] / M) will evaluate to k for the maximum element (where array[i] = M). This could be amended if M was set to max(array) + 1, though this feels kind of hacky. Any better suggestions?

Also note: A lot of publications assume the values of the elements in the array to lie in the half-closed interval [0,1). In that case, placing element array[i] into buckets[floor(k × array[i])] works. OwlSurojit (talk) 11:39, 6 October 2022 (UTC)

sorting negative numbers

The pseudocode does not accept sorting negative numbers. If array[i] < 0 then the expression floor(k × array[i] / M) is evaluate to a negative index. 109.99.125.198 (talk) 11:38, 18 February 2023 (UTC)