Limitations of comparison based sorting techniques

Question

Comparison sort is opted for in most of the scenarios where data needs to be ordered. Techniques like merge sort, quick sort, insertion sort and other comparison sorts can handle different data types and efficiency with a lower limit of O(nLog(n)).

My questions are

1. Are there any limitations of comparison based sorting techniques?
2. Any sort of scenarios where non-comparison sorting techniques would be used?

cheers

Answer 1

You answered it more or less yourself. Comparison based sorting techniques are limited to lower limit of O(n Log(n)). Non-comparison based sorting techniques do not suffer from this limit. The general problem with non-sorting algorithms is that the domain must be better known and for that reason they aren't as versatile as comparison based techniques.

Pigeonhole sort is a great and quite simple example which is pretty fast as long as the number of possible key values is close to the number of elements.

Answer 2

Obviously the limitations of comparison sorts is the time factor - some are better than others, but given a large enough data set, they'll all get too slow at some point. The trick is to choose the right one given the kind and mix of data you're sorting.

Non-comparison sorting is based on other factors ignoring the data, eg counting sort will order a collection of data, by inspecting each element - not comparing it with any other value in the collection. Counting sort is useful to order a collection based on some data, if you had a collection of integers, it would order them by taking all the elements with a value of 1 and putting them into the destination first, then all elements of value 2 etc (ok, it uses a "sparse" array to quickly zoom through the collection and reorder the values, leaving gaps but that's the basic principle)