Is it possible to invent a sorting algorithm for less than O(n)?

Question

Currently for a large randomly generated array of elements lets say array of int can be sorted within O(n logn). Is it possible to invent a sorting algorithm for O(n) or less than O(n)? What is the theoretical limit and how do we proof that limit?

Answer 1

No, you cannot have a sorting algorithm that runs in less than $\mathcal{O}(n)$ time. Suppose you want to sort a list of $n$ numbers. You must always look at all $n$ numbers, and this process itself runs in $\mathcal{O}(n)$ time.

There are some $\mathcal{O}(n)$ sorting algorithms that exist, but they are not comparison-based sorting algorithms, and they all assume some information about the numbers being processed (see, for example, counting sort, bucket sort, or radix sort). It is has been proven that a comparison-based sorting algorithm cannot run faster than $\mathcal{O}(n\log n)$ time.