algorithmmergesort

Non-Recursive Merge Sort

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

Thanks

Solution

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