Search code examples
javasortingstreamquicksortbucket-sort

Bucket Sort vs Quick Sort

General Question: Why is Bucket Sort more beneficial that Quick Sort?

Lets say numbers are incoming from a stream, and my buckets are like (1,10) (11,20) ect ect.

Then I sort the buckets and then put them together, having my sorted numbers.

OR

I can put them in an array, and then sort them with Quicksort

  • Bucket Sort: Bestcase O(N + K) worstcase (N^2);
  • Quicksort: Bestcase O(1) Averagecase O(nlogn) worstcase (N^2);

So why do we use bucket sort for things like streams of incoming integers that we want sorted? Is it because we can make decisions based on the number of integers in each of your buckets?

Thanks

Solution

  • If we know k up front, and it is small (k << n) then bucket sort can efficiently run faster than Quicksort, since n*log(n), the average for Quicksort, will be more than (n + k), which is the average for bucket sort.

    I.e., 

    sortedList = (n*log(n) > n + k) ? bucketSort(list) : quicksort(list);

    A reason it may be used for streams, is that bucket sort is in-place. You can maintain the sorted list, adding new elements efficiently, without having to re-sort it every time. You just manipulate the data structure (bucket) directly, and that's it.

    Quicksort on the other hand, is not in-place, and requires a full sorting run in order to return the sorted list.