# Is it possible to make partition of Quicksort run in O(lg n)?

I was thinking maybe I can make it 2T(n/2) + C split the list into two halves and work on them recursively to partition the list.

• Does your question asks whether it is possible to find median in logarithmic time (to split into two halves)? The answer is no, it is not possible to find median faster than linear time in unsorted array under general assumptions. – Evil Mar 14 at 22:03
• $T(n) = 2T(n/2) + C$ gives $T(n) = \Theta (n)$ – Peter Taylor Mar 15 at 7:12

No. The partition operation must access every item in the list: if there is any item it does not look at, then you don't know which side of the partition it belongs on. Consequently, the partition operation cannot run any faster than $$O(n)$$ time, where $$n$$ is the length of the list.
Mathematically, you're confusing the recurrence $$T(n)=2T(n/2)+c$$ with the binary search recurrence $$T'(n)=T'(n/2)+c$$. $$T'=\Theta(\log n)$$ but $$T(n)=\Theta(n)$$. In binary search, you only have to recurse on one half; having to visit both halves kills you.
In fact, it's probably even worse. Saying that your partitioning scheme runs in time $$T(n)=2T(n/2)+c$$ is saying that you can combine the partitions of the two halves in constant time. The only way I can think of doing that would be using some kind of linked list data structure. But then splitting the list requires finding the middle, which is still $$\Theta(n)$$. Maybe you could do something with binary trees but, man, this is getting complicated and your best possible outcome is a complicated way of getting the $$\Theta(n)$$ partitioning time we already had with the simple algorithm on an array.