2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ How can you do it with priority queue that fast? Something is wrong as wikipedia says that this is lower bound when using comparisons for sorting. $\endgroup$ – rus9384 Aug 26 '17 at 11:04
  • $\begingroup$ It is not hard to do, we put in priority queue the first element from all arrays, then when we take one element from one array, we put in the queue the next one... we just need to keep index where are we in each array $\endgroup$ – someone12321 Aug 26 '17 at 11:07
  • $\begingroup$ If your only access to elements is by comparing them and moving them around, then there is an $\Omega(n\log n)$ lower bound. If your elements are integers and you're not restricting yourself, then better algorithms are known. $\endgroup$ – Yuval Filmus Aug 26 '17 at 11:08
  • $\begingroup$ Note that $O(n\log n)$ and $O(n\log\sqrt n)$ are the same complexity class. $\endgroup$ – Yuval Filmus Aug 26 '17 at 11:09
  • $\begingroup$ @YuvalFilmus, I was thinking that this algorithm will work faster, but the implementation is pretty hard, so it is not really good to implement this, can you give me some resources about learning more sorting techniques $\endgroup$ – someone12321 Aug 26 '17 at 11:12
8
$\begingroup$

You got a result of $O(N⋅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 \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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.