If merge sort is the best answer, then I think half the point might be to then ask "How long does it take?" My thinking is imagine this problem is solving a partially completed merge sort. There are M*N elements, so a standard, full merge sort would have taken O(MN log(MN)), but we have less work to do than that (if N > 1). In standard merge sort, we have MN work at each stage, each stage merging all of the small arrays together to make arrays twice as large, and there are log(MN) stages. Here, we only have log(M) stages left before we have a fully merged array, so this algorithm should take O(MN log(M)) time.