CODEWITHSUNDEEP
algorithmsorting
Waley Chen
Waley Chen

Reputation: 929

What are the main disadvantages of Non-Comparison-Based Sorting Algorithms versus Comparison-Based Sorting Algorithms?

I'm trying to understand the main disadvantages of non-comparison-based sorting algorithms to comparison-based sorting algorithms.

Is it mainly because non-comparison-based sorting algorithms do poorly for non-fixed length inputs?

e.g. let's say I had 4 elements [1, 100000000000000000024, 3, 5]

A comparison-based sorting algorithm would solve it in 4 * log(4).

While a non-comparison-based sorting algorithm would solve it in 4 * length_of("100000000000000000024") assuming we use the keys 0 to 9 and use an algorithm such as LSD or MSD.

Or let's say we know the numbers fall between 0 and 100000000000000000024, we could have keys from 0 to 100000000000000000024, but that's extremely space inefficient as comparison-based sorting algorithm can be done in-place.

Thanks, Waley

Upvotes: 0

Views: 1344

Answers (1)

kudkudak
kudkudak

Reputation: 496

Non-Comparison sorting algorithms often need many assumptions about the input data (integers from small range for count sort, uniformly distributed for bucket sort, etc.).

The time complexity is also often dependent on only on the input size. For instance count sort depends on the range, as well as the radix sort.

Upvotes: 3

Related Questions