Can we create faster sort algorithm than O(N log N)

Question

I was thinking that we can create algorithm for sorting that will work faster than $O(N\log N)$

Let's say we have given array $A$ consisting of $N$ integers, where $N = 10^6$. Our task is to sort this given array. The clear solution is to sort the array using the classic merge sort algorithm, which works in $O(N \log N)$ time and space complexity. I was thinking that this trick can improve the complexity.

Let $N_{1} = 10^5$, clearly $N = 10\cdot N_{1}$. Let's split the array $A$ in $10$ smaller array where each array consist of $N_{1}$ elements and sort those $10$ arrays with standard merge sort ( time complexity: $O(N_{1}\cdot\log N_{1})$), so we have 10 arrays where each array is sorted, we can merge those 10 array into one array in time complexity $O(N\cdot\log(10))$ using priority queue.

So the total complexity will be $O(10 \cdot N_{1}\cdot\log N_{1} +N\cdot\log(10))$. Now let's say we split the array in $\sqrt{N}$ arrays, so the complexity will look like: $$O(\sqrt{N} \cdot \sqrt{N} \cdot \log \sqrt N + N \cdot \sqrt N)\\ = O(N \cdot \log (\sqrt N) + N \log (\sqrt N))$$

Is everything in my algorithm correct, and is this trick efficent in memory usage?

Answer 1

You got a result of $O(N\cdot \log(\sqrt N)+N\log(\sqrt N))$.

But $\log \sqrt N = (\log N)/2$, so $N⋅log(\sqrt N)+N·\log(\sqrt N) = N·\log N$. So not only is it the same complexity class, where constant factors don't matter, it is even the same function, therefore the same constant factor.

But the underlying reason for any comparison based sorting algorithm to take $O(\log N)$ comparisons is that there are N! possible permutations of the array elements, each comparison can rule out at most half the possible cases, so you absolutely need at least $\log_2 N!$ comparisons in the worst case, which is $O(N\cdot \log N)$. That $\log_2 N!$ is not a big-O, it is an absolute number. You cannot achieve for example $0.999 \log_2 N!$ comparisons in the worst case.

So you would have to come up with an algorithm that isn't based on comparison. For example, if an image contains pixels using 24 bits each, then you can sort the $N$ pixels of an image in $O(N)$ (see "The Player of Games" for reasons why you would want to sort all the pixels in a large library).

Answer 2

Your example is an unfortunate one. Since you are sorting integers, you can pose a specific requirement to sort, such as the value, if that is the only thing to sort on you can use the radix sort, which would put the complexity at O(#ofdigitsn) or O(kn) which is 99% of cases is much better than lg(n), the only reason is sorting alrogithm isn't used more often is because it is too restrictive with the type of data it can sort.

For example: If you had 10^6 integers in the worst cause scenario, because integers can only have 8 digits, you would have 8*10^6 calculations for radix sort, but for MergeSort you would have 20*10^6 which is significantly slower.