53

Bucket sort and radix sort are close cousins; bucket sort goes from MSD to LSD, while radix sort can go in both "directions" (LSD or MSD). How do both algorithms work, and in particular how do they differ?

Lazarus
  • 531
  • 1
  • 4
  • 4

2 Answers2

50

The initial pass of both RadixSort and BucketSort is exactly the same. The elements are put in buckets (or bins) of incremental ranges (e.g. 0-10, 11-20, ... 90-100), depending on the number of digits in the largest number.

In the next pass, however, BucketSort orders up these 'buckets' and appends them into one array. However, RadixSort appends the buckets without further sorting and 're-buckets' it based on the second digit (ten's place) of the numbers. Hence, BucketSort is more efficient for 'Dense' arrays, while RadixSort can handle sparse (well, not exactly sparse, but spaced-out) arrays well.

Vlad Schnakovszki
  • 8,434
  • 6
  • 80
  • 114
Akash
  • 501
  • 3
  • 2
  • 4
    Could you expand this answer to explain why the time complexities of these two methods are different? i.e. why is bucket sort O(n+k), but radix sort is O(nk)? – Shaun Budhram Feb 23 '15 at 09:24
  • 2
    @ShaunBudhram It is old question, but if someone reading this wants to know. It is apparent from the description, bucket sort does one pass on N, and then merges K buckets (order within bucket is arbitrary). Whereas radix sort does one pass for each bucket, here I think sorting of strings would be better example, so you do K passes of complexity N. – Vojtěch Kaiser Feb 28 '16 at 12:15
  • What do you mean by "BucketSort orders up these 'buckets'"? Is each bucket sorted with a different algorithm or what? Because each bucket isn't fully sorted if you group by 10s. – mpen Oct 24 '17 at 20:11
  • "Hence, BucketSort is more efficient for 'Dense' arrays, while RadixSort can handle sparse arrays well." - why is this the case? – Shuklaswag Sep 10 '18 at 17:31
26

Bucket Sort and Radix Sort are like sister sorting algorithms because they are not comparison sorts and the general idea is similar. Also, they both are a bit abstract in implementation.

Radix Sort:

  • Radix means base(binary, octal, decimal,etc). Therefore, this sorting is for numbers (also used for strings). This works when each element E is like ek...e2e1e0, where ei is in some range. (usually 0 to a base like 0-9 in decimal or 0-255 in ASCII characters)

  • It then uses k passes of a stable sub-sorting algorithm (It has to be stable or else Radix sort won't work) to sort the numbers. This sub-sorting algorithm is usually Counting sort or Bucket sort as well but it cannot be Radix sort itself.

  • You can start from Most Significant Digit or Least Significant Digit because it shuffles every number in each pass (from k to 0 or 0 to k)

  • It is a stable sorting algorithm.

Bucket Sort:

  • It separates array into smaller groups or buckets and sorts them individually using a sub-sorting algorithm or recursive call to itself and then combines the result. For example, sorting players by adding into buckets of their team then sorting them by their jersey numbers or something like sorting numbers from ranging from 1-30 into 3 buckets of 1-10, 11-20, 21-30.

  • The combine step is trivial (unlike merge sort). just copy elements of each bucket back into original array or join the head of each bucket with tail of previous bucket (in case of linked lists)

  • Radix/base could be a type/instance of the group/bucket while sorting numbers. Therefore you could think of MSD radix as a modified instance of bucket sort

  • Bucket sort is not in-place but stable sorting algorithm. However, some variations of bucket sort might not be stable (if you use a sub-sorting algorithm which is not stable)

Rob
  • 3,333
  • 5
  • 28
  • 71
dev_ankit
  • 516
  • 4
  • 8