Summary

Bottom-up merge sort starts with runs of length one and repeatedly merges neighboring runs. It replaces recursion with passes of width 1, 2, 4, and so on.

How it Works

• Treat every item as a sorted run of length one.

• Merge adjacent runs into a temporary buffer, choosing the left item on ties.

• Double run width after each full pass until one sorted run remains.