Merge Sort Builds Order by Merging Sorted Ranges

Merge sort earns its order after the array has been split into one-element ranges

Start with the running array [6, 3a, 8, 2, 5, 3b, 7, 1] in the half-open range [0, 8). Merge sort splits this range at its midpoint, producing [0, 4) and [4, 8). Each of those ranges is split again, until the array has eight ranges: [0, 1), [1, 2), [2, 3), [3, 4), [4, 5), [5, 6), [6, 7), and [7, 8).

A range containing one value is already sorted, so it is the base case where recursion stops. For example, [1, 2) contains only 3a, and no rearrangement can improve its sorted order. Splitting does not sort the original array by itself. It only creates small ranges whose order is known, giving the later merge step a reliable starting point.

A merge needs to compare only the two front unconsumed values

After the smaller ranges have been merged, the running array reaches two sorted runs: the left run [2, 3a, 6, 8] and the right run [1, 3b, 5, 7]. A pointer marks the first unconsumed value in each run. The next output must be the smaller of those two front values, because every later value in either run is at least as large as its front value.

left:  [2, 3a, 6, 8]    right: [1, 3b, 5, 7]
compare 2 and 1 -> output 1
compare 2 and 3b -> output 2
compare 3a and 3b -> output 3a
compare 6 and 3b -> output 3b
compare 6 and 5 -> output 5
compare 6 and 7 -> output 6
compare 8 and 7 -> output 7
right run exhausted -> copy 8

The pointers advance only in the run that supplied the output value. When the right run is exhausted, its pointer can no longer participate in a comparison, but the left run is still sorted and its remaining values are already in the correct order. Copying those remaining values gives the complete result [1, 2, 3a, 3b, 5, 6, 7, 8]. The same rule applies when the left run is exhausted first.

Half-open ranges and one temporary array keep every boundary exact

A top-down implementation can represent every range with sort(left, right), where left is included and right is excluded. Its base condition is right - left <= 1. Otherwise, calculate mid = left + (right - left) / 2, sort [left, mid), sort [mid, right), and merge those two sorted ranges into [left, right).

void sort(int left, int right) {
    if (right - left <= 1) return;

    int mid = left + (right - left) / 2;
    sort(left, mid);
    sort(mid, right);

    int i = left;
    int j = mid;
    int k = left;

    while (i < mid && j < right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i < mid) temp[k++] = arr[i++];
    while (j < right) temp[k++] = arr[j++];

    for (int p = left; p < right; p++) {
        arr[p] = temp[p];
    }
}

The merge uses i for the left run, j for the right run, and k for temporary storage. The first loop compares the two front values while both runs still have values. The two following loops copy whichever run remains. Finally, only indices from left through right - 1 are copied back. No statement reads or writes index right, so adjacent ranges do not overlap by accident.

while (??? ) temp[k++] = arr[i++];

Each merge level processes all eight elements once

For the running array with n = 8, the bottom merge level joins four pairs of one-element ranges. Each pair processes two values, so the level processes 8 values in total. The next level joins two pairs of two-element ranges, again processing 8 values. The final level merges two four-element ranges and processes 8 values once more.

There are log2(n) merge levels because each split doubles the number of ranges until there are n one-element ranges. Each level does O(n) work, so the time complexity is O(n log n). The temporary array uses O(n) space and can be reused by every merge. The recursion depth is O(log n), because one recursive path keeps halving its range.

Taking 3a before 3b preserves their original order

The two values marked 3a and 3b have the same numeric value, but 3a appeared first in the original array. When the merge compares equal front values, choosing the value from the left run first preserves that original order. The tie rule is written with <=, so the completed array is [1, 2, 3a, 3b, 5, 6, 7, 8].

if (arr[i] <= arr[j]) {
    temp[k++] = arr[i++];
} else {
    temp[k++] = arr[j++];
}

Changing <= to < still produces numeric sorted order, so the output may look correct if you inspect only the values. However, equal values are then sent to the right run whenever they meet. Depending on how the tagged elements were divided and merged, that choice can place 3b before 3a. The <= rule makes the merge stable: equal values keep their order from the input.