How merge sort works at arrays of length N?
Mia Lopez 
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?
32 Answers
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.
4A non recursive merge sort treats an array of N elements as N sorted runs of size 1, then merges even and odd runs from one array to another array. If there are an odd number of runs, the last one is just copied (nothing to merge it with), this may be taken care of in the merge() function. After a merge pass is done, the run size is doubled to 2, and the merge process is repeated. When the run size is doubled and is >= array size, the merge sort is done.
The code maintains 3 indexes: start of the left run, start of the right run (== end of left run), end of right run. While setting up or advancing the indexes, if an index becomes >= size of array, it's reduced to the size of the array. If this happens on the left run, then that is the last and odd run, so it is copied (again, this may be handled within a merge() function).
Wikipedia has pseudocode:
