snippetModerate
Can we create faster sort algorithm than O(N log N)
Viewed 0 times
cancreatelogthanfasteralgorithmsort
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#80458, answer score: 13
Revisions (0)
No revisions yet.