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
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.