Given an array arr[], its starting position l and its ending position r. Sort…

Concept: merge sort rests on a single fact — two sequences that are each already sorted can be combined into one sorted sequence in a single linear pass, by repeatedly moving the smaller of the two front elements to the output. Sorting a range therefore reduces to sorting its two halves and then merging them, so the algorithm is defined recursively on a range [l, r]: split at m = l + (r - l) / 2, sort [l, m] and [m + 1, r], then merge the two sorted halves. A range holding a single element is already sorted, and that is the base case that stops the recursion.

Application to arr[] = [4, 1, 3, 9, 7] with l = 0 and r = 4:

1. Split the range at m = 2, giving the halves [4, 1, 3] and [9, 7]. No values are compared here — the split is purely positional, which is why merge sort behaves identically on every input of the same size.

2. Sort [4, 1, 3]: it splits into [4, 1] and [3]. [4, 1] splits into the single elements [4] and [1]; merging those compares 4 with 1, emits 1, then emits the leftover 4, giving [1, 4].

3. Merge [1, 4] with [3]: compare 1 with 3 and take 1; compare 4 with 3 and take 3; the right run is now empty, so the leftover 4 is appended. This half becomes [1, 3, 4].

4. Sort [9, 7]: it splits into [9] and [7]; merging compares 9 with 7, emits 7, then emits 9, giving [7, 9].

5. Merge [1, 3, 4] with [7, 9]: 1, 3 and 4 are each smaller than 7, so they leave first; the left run is then empty and the tail 7, 9 is copied across. The result is [1, 3, 4, 7, 9], which matches the expected output.

Cross-check: the output is non-decreasing and is a permutation of the same multiset {1, 3, 4, 7, 9} that went in — the two properties every correct sort must satisfy. The second example, [10, 9, 8, 7, 6, 5, 4, 3, 2, 1], is the fully reversed input that drives many quadratic sorts to their worst case, yet merge sort splits it in exactly the same way and moves exactly the same number of elements, because it splits by position and never by value; only the number of key comparisons made inside each merge varies with the data.

Why the cost is of the order n log n — the total work is the same at every recursion level. Take n to be a power of two, so that every split is exact; for any other n the two halves differ by at most one element, so the accounting below changes only by rounding:

The deepest level holds n single-element ranges; those are already sorted and are never merged, so merging happens at levels 0 through log2 n - 1 — that is log2 n levels, each costing n. In general that is the recurrence T(n) = T(ceil(n / 2)) + T(floor(n / 2)) + n, which for a power of two is written T(n) = 2T(n / 2) + n; either way its solution is of the order n log n.

• Time: of the order n log n in the best, average and worst case alike, because the split is positional and each merge scans every element of its range exactly once.

• Auxiliary space: proportional to n for the temporary buffer the merge writes into — the trade merge sort makes against in-place sorts such as heap sort.

• Stability: the merge preserves the relative order of equal keys provided it takes from the left run on a tie, that is, it compares with left <= right rather than left < right.

• Under the stated limit arr.size() ≤ 105, n log2 n is about 1.7 million elements written into the merge buffer, and as many copied back, which sits comfortably inside the time limit.

Two implementation pitfalls worth naming: computing the midpoint as (l + r) / 2 can overflow a fixed-width integer for large indices, so m = l + (r - l) / 2 is the safe form; and after the main comparison loop the merge must still copy across the tail of whichever half is not yet exhausted, otherwise the largest elements are silently dropped.