is there any linear sorting algorithm?

Question

Hi, is there any linear sorting algorithm with complexity of O(n), if not why? and what's the best sorting algorithm?

Answer 1

It can be proved that any comparison sort (that is, the ones that are based on operators like "<=") take at least O(n log n) time in the worst case scenario.

Each comparison gives us one True/False result. So k comparisons would create 2^k possibilities. On the other hand there are n! ways the input can be arranged. So in order to make sure the algorithm actually handles all possible cases, we need

2^k >= n!
Or, k >= log_2 (n!)

So that gives us O(k) = O(log n!) = O(n log n)* time complexity. Examples of sorting algorithms that achieve this bound are quick sort, merge sort, heap sort, etc.

However, for integers, there are other non-comparison algorithms that can sometimes perform faster than O(n log n). Their complexities depend on a few other factors. Examples: counting sort, radix sort. Check out this list here:
https://en.m.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

* Stirling's approximation for factorial

Answer 2

Let's try a different angle. Say we have n=3 elements: a, b, c. For simplicity, assume they are distinct. There are 3! = 6 possible cases:
a<b<c
a<c<b
b<a<c
b<c<a
c<a<b
c<b<a

Think of ourselves as detectives solving a murder crime: those 6 are our suspects, and we want to narrow it down to 1: the correct order for a particular case.

Say our code uses k pairwise comparisons. Each of them is a new "clue" that reduces the number of "suspects" by at most half. For example, starting from the initial 6 cases, when we know the result of the comparison "b<c" is true, we only have to consider these 3: a<b<c, b<a<c, b<c<a.

Thus after k comparisons, we have reduced the number of possibilities by 1/2^k at best. Since we started with n! possibilities and wish to finish with just 1, we get

n! / (2^k) <= 1, as required.

("<=", because having more comparisons doesn't hurt, though they won't give us anything new.)

Answer 3

A very nice example, Jay!

Just for some "elaboration": I think it can be described as a special case of the pigeonhole sort (which is further generalized to bucket sort). It is a non-comparison type sort, so it doesn't break the O(n log n) bound I mentioned. This specific example requires the inputs to be distinct, consecutive integers (not necessarily "consecutive" in the order they are given, obviously). And yes, if those conditions are met, it would be linear :)

Read more on pigeonhole sort here:
https://en.wikipedia.org/wiki/Pigeonhole_sort

Edit: PaintingJo , sorry for repeating some of your words. I didn't see your comment. I had this post open for a while 😂

Answer 4

Jay Matthews, another downside is that you need an array in which all indexes contain a different value, and the values must be between 0 and the array's length-1. Else you will skip sorting certain indexes and/or get out of the array's bounds.

In other words, you must have an array of length N containing values 0 through N-1.

Answer 5

Kishalaya Saha That was a nice explanation, but i have a doubt, how did you conclude 2^k >= n! ? I cant visualize that, like if we have 3 elements in an array, then it can be arranged in 3! = 6 ways, how do we need, 2^k comparisons here and what should be the k and why it should be such that 2^k is bigger than n! ?

Answer 6

Kishalaya Saha That was a very nice explanation, explained in such an easy way, thank you for that.

Answer 7

You're most welcome, Mayank! 😊