Non-Recursive Merge Sort

Question

Can someone explain in English how does Non-Recursive merge sort works ?

Thanks

Answer 1

Quoting from Algorithmist:

Bottom-up merge sort is a non-recursive variant of the merge sort, in which the array is sorted by a sequence of passes. During each pass, the array is divided into blocks of size m. (Initially, m = 1). Every two adjacent blocks are merged (as in normal merge sort), and the next pass is made with a twice larger value of m.

Answer 2

Loop through the elements and make every adjacent group of two sorted by swapping the two when necessary.

Now, dealing with groups of two groups (any two, most likely adjacent groups, but you could use the first and last groups) merge them into one group be selecting the lowest valued element from each group repeatedly until all 4 elements are merged into a group of 4. Now, you have nothing but groups of 4 plus a possible remainder. Using a loop around the previous logic, do it all again except this time work in groups of 4. This loop runs until there is only one group.