Can someone explain to me what each loop, and variable means in Bottom up Merge Sort?

Question

I am having a rough time understanding the Pseudocode for the bottom up merge sort algorithm.

Conceptually, I sort of understand what's taking place.

1. we iterate through the array and separate each element into it's own array
2. we merge the first two adjacent arrays (containing 1 element each) to create a new sorted array of 2 elements.
3. we iterate through the array again, this time doubling the amount of elements placed into a new array. These elements have already been sorted by the previous merge and iteration step.
4. we merge the first two adjacent arrays (this time containing 2 sorted elements each) to create a new sorted of array of 4 elements.
5. this process continues until the entire array is sorted.

I'm looking at the pseudocode from this site - http://www.algorithmist.com/index.php/Merge_sort

Input: array a[] indexed from 0 to n-1.

m = 1
while m < n do
    i = 0
    while i < n-m do
        merge subarrays a[i..i+m-1] and a[i+m .. min(i+2*m-1,n-1)] in-place.
        i = i + 2 * m
    m = m * 2

But I am getting lost after the first while loop! The recursive implementation was more intuitive for me, but the iterative approach is throwing me off! If anyone can implement it in python or c++, and explain each step, and what each variable is for I would greatly appreciate it.

Cheers!

Answer 1

m is the number of elements being sorted together. It starts with 1 element, and keeps doubling until we've merged one half of the list with the other half.
n is the size of the list.
i is the index of the first element of the first subarray being merged.
i + m is the first element of the second subarray being merged.

Here's a simple example.

Say I have the following n=5 list: a = [3,1,2,5,4]

m = 1:
    Merge each 1 element subarray with its 1 element neighbor subarray

    i = 0:
        Merge [3] and [1] -> [1,3]
        a is now [1,3,2,5,4]

    i = 2:
        Merge [2] and [5] -> [2,5]
        a is now [1,3,2,5,4]

m = 2:
    Merge each 2 element subarray with its 2 element neighbor subarray

    i = 0:
        Merge [1,3] and [2,5] -> [1,2,3,5]
        a is now [1,2,3,5,4]

m = 4:
    Merge each 4 element subarray with its 4 element neighbor subarray

    i = 0:
        Merge [1,2,3,5] and [4]
        a is now [1,2,3,4,5]. We're done sorting.