Halving is the the operation that takes an array A with n distinct numbers and separates it into two half-sized1 arrays A0 and A1, where all elements of A0 are smaller than all elements of A1. (Note that it is not required that A0 and A1 are sorted. ) Prove that Halving can be done in linear time by presenting an algorithm and arguing its correctness and justifying the running time. You can describe the algorithm in words, if you wish. Just make it clear. You may also invoke any algorithms discussed in lecture in a black-box fashion without having to reprove its correctness
