How to divide an unsorted list into two equal parts in linear time, where every element in the first part is smaller than every element in the second part

I tried to use QuickSort but in can result in $O(n^2)$ worst-case time complexity.

  • $\begingroup$ Find median in log or linear time, then in one pass apply the same algorithm as you would to sort a vector of 0s and 1s $\endgroup$
    – Matthew C
    Dec 10 '19 at 15:14

Use the median of medians with quickselect allows you to find the $k$th element in linear time. Set $k = n/2$ to find the exact median and use it to partition your array in one more linear time step.


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.