Merging two ordered runs
Two ordered runs can be merged by repeatedly comparing their next unconsumed items and outputting the smaller. When one run is exhausted, the remaining tail of the other is copied. Each element advances through this merge once, making work linear in the combined length.
Both inputs must already be sorted. Looking only at their fronts would otherwise miss a smaller item hidden later. Merge sort first establishes sorted subproblems and then uses that condition to justify the merge.
References: [1]
Top-down and bottom-up organization
Top-down merge sort recursively sorts two halves and merges them, stopping at runs of length at most one. Linear work per level across logarithmically many balanced levels gives O(n log n) worst-case time under constant-cost comparisons.
A bottom-up version instead merges adjacent singleton runs, then runs of length two, four, and so on. It uses the same merge principle without recursive splitting. Recursion is one organization of the algorithm rather than its defining requirement.
Storage, stability and skipped merges
A common array version copies into auxiliary storage before merging back, requiring Θ(n) extra space. Choosing the left item first on equality preserves equal-key order; stability depends on that rule.
A boundary check can skip a merge when the two sorted halves already fit together, but the basic version need not include it. In-place merging, linked representations and other run strategies have different requirements, so resource claims should identify the implementation.