Given an input array of n numbers, we want to separate the smaller n/2 numbers and put them in the left half of the array and the larger n/2 numbers in the right half of the array. Does the sorting lower bound apply to this problem? Justify your answer. Design an efficient (worst-case) algorithm for this problem and analyze its complexity.

Answer rating: 100% (QA)

A lower bound for a problem is the worstcase running time of the best possible algorithm for that ... View the full answer