CODEWITHSUNDEEP
algorithm
PURNIMA
PURNIMA

Reputation: 1

Why is bucket sort considered to be non-comparison sort?

Why is Bucket sort considered to be a non-comparison based sorting algorithm (where no comparison of keys is performed for sorting the list) despite the fact that insertion sort, which is used to sort individual buckets is comparison based ?

Upvotes: 0

Views: 1324

Answers (1)

trincot
trincot

Reputation: 351021

Insertion sort is indeed a comparison sort, so you are right that if the buckets are sorted using insertion sort, and that is considered an integral part of bucket sort, then we should also call it a comparison sort.

But:

  • The same happens in other algorithms as well. Quick sort and merge sort implementations will often switch to insertion sort when the partition becomes smaller than a certain threshold. To be entirely transparent, you should then say that these algorithms are a mix of two algorithms, and not pure quick sort, merge sort, and ... bucket sort.

  • There is no rule that bucket sort must use another sorting algorithm to sort the buckets. Bucket sort can be implemented in a pure way, i.e. by sorting the buckets recursively using bucket sort, until all buckets have at the most 1 value.

Actually, the Wikipedia article on bucket sort, addresses this consideration in the opening paragraph:

...Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort [...]. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm.

Upvotes: 1

Related Questions