How merge sort works at arrays of length N?

Question

I've hit the books and was faced with problem i can't solve. I have been looking the information up a long. I broke my mind trying to understand it.

So, I'm given an array of length N (int) to sort it by using non-recursive merge sort algorithm. I learned merge sort algorithm for arrays of length 2^n. But I totally can't understand how it works for arrays of length N.

Can someone explain me how it works?

Answer 1

Given seven elements, the subtask tree looks like this:

          [3,5,2,1,4,7,6]
             /         \
      [3,5,2,1]        [4,7,6]
      /       \        /      \
   [3,5]    [2,1]    [4,7]    [6]
   /   \    /   \    /   \    /
 [3]  [5]  [2]  [1] [4]  [7] [6]

The idea is that you split the array "in half" at each level. If an array has an odd number of items, then splitting it will result in one subarray will have one more item than the other. It doesn't make the problem any more difficult: merging two arrays of different length is no trouble.