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.