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.
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!
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.