# How to divide an unsorted list in linear time where every element in the first part is smaller than every element in the second list

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.

• 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 – Matthew C Dec 10 '19 at 15:14

## 1 Answer

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.