CODEWITHSUNDEEP
sorting
Luigi Massa Gallerano
Luigi Massa Gallerano

Reputation: 2357

No key-comparison sorting algorithm

On this webpage I can read:

A few special case algorithms (one example is mentioned in Programming Pearls) can sort certain data sets faster than O(n*log(n)). These algorithms are not based on comparing the items being sorted and rely on tricks. It has been shown that no key-comparison algorithm can perform better than O(n*log(n)).

It's the first time I hear about non-comparison algorithms. Could anybody give me an example of one of those algorithms and explain better how they solve the sorting problem faster then O(nlog(n))? What kind of tricks the author of that webpage is talking about?

Any link to papers or other good source are welcome. Thank you.

Upvotes: 2

Views: 989

Answers (2)

NPE
NPE

Reputation: 500475

First, let's get the terminology straight:

  1. Key comparison algorithms can't do better than O(n logn).
  2. There exist other -- non-comparison -- algorithms that, given certain assumptions about the data, can do better than O(n logn). Bucket sort is one such example.

To give an intuitive example of the second class, let's say you know that your input array consists entirely of zeroes and ones. You could iterate over the array, counting the number of zeroes and ones. Let's call the final counts n0 and n1. You then iterate over the output array, writing out n0 zeroes followed by n1 ones. This is an O(n) sorting algorithm.

It has been possible to come up with a linear-time algorithm for this problem only because we exploit the special structure of the data. This is in contrast to key comparison algorithms, which are general-purpose. Such algorithms don't need to know anything about the data, except for one thing: they need to know how to compare the sorting keys of any two elements. In other words, given any two elements, they need to know which should come first in the sorted array.

The price of being able to sort anything in any way imaginable using just one algorithm is that no such algorithm can hope to do better than O(n logn) on average.

Upvotes: 8

Ayman Farhat
Ayman Farhat

Reputation: 2080

Yes non comparison sorting usually takes O(n) an example of these sorting algorithms are the Bucket Sort and Radix Sort

Upvotes: 1

Related Questions