Solve the interleaving first and second halves of an array with O(nlgn) solution. O(n^2) solution is added in the comment as well.