We have explained why the minimum theoretical Time Complexity of non-comparison based sorting problem is O(N) instead of O(N logN). This is a must read. It will open up new insights.

Table of content:

1. How to do Sorting without comparison?
2. Time Complexity bound for non-comparison based sorting
3. Conclusion

To short:

• Time Complexity Bound for non-comparison based sorting: O(N)
• Time Complexity Bound for comparison based sorting: O(N logN)

How to do Sorting without comparison?

The analysis we did for the previous few chapters is for sorting algorithms based on comparison. It may seem obvious that we cannot optimize it further, but the truth is we can.

The loophole is that comparison is not necessary for sorting. This is not a simple statement so think about this deeply.

A sorting problem can be seen as a:

• Comparison problem
• Ordering problem
• Matching problem

The idea is if we have an already sorted list, we can sort any list just by matching the ordering of the second list to the first already sorted list.

This process does not require comparison.

Time Complexity bound for non-comparison based sorting

To find the theoretical limit of a problem, we need to consider different ways to handle the problem. Note formulating the actual algorithm is not necessary.

The theoretical limit is O(N) for sorting as we need linear time for a matching problem. Consider the problem of matching each element to be even or odd. Sorting is a similar problem as comparison is always between two elements.

Matching problem for Sorting:

• Given a number N, we need to match another element M to be before N (that is < N) or after M (that is > N).

This matching can be done without using comparison using specific data structure like bucket array.

Another way to think about this is as we need to process all elements, so sorting cannot be done lower than O(N). The best we can do is O(N) while analysis of comparison-based sorting shows lower limit is O(N logN).

Counting sort, radix sort and bucket sort are some of the non-comparison-based sorting. These algorithms make no comparison. These are also known as linear sorting algorithms. They do not need a comparison decision tree.

Counting sort uses the key values for sorting, where N is the number of inputs and K is the maximum element. Counting sort takes O(N+K) time which is better than comparison-based sorting. If N is as large as K then this is O(N). Since non-comparison-based sorting algorithms don't make a comparison, it allows sorting at linear time.

Conclusion

Approach/ Algorithm for a Problem is very important. As you see if we are focused on improving Comparison based Sorting, the we are stuck in O(N logN).

If we take a new approach and view sorting as a matching problem, then we get to O(N) which is a significant improvement.

You must go through the Time Complexity of some non-comparison based sorting algorithms:

• Analysis of Counting Sort
• Analysis of Bucket Sort
• Analysis of Radix Sort

With this article at OpenGenus, you must have the complete idea of Time Complexity Bound for Non-comparison based sorting algorithms.