Merge Sort

Merge Sort and Divide-and-Conquer

Merge sort divides a sequence into two smaller ranges, recursively sorts each range, and merges the two sorted results. The base case is a range of zero or one element. Unlike elementary quadratic sorts, its running time remains Θ(n log n) even for reverse-ordered input.

1. Divide: choose the midpoint of [left,right).
2. Conquer: sort [left,middle) and [middle,right).
3. Combine: merge both ordered ranges into one ordered range.

Half-open ranges make lengths, empty ranges and adjacent partitions precise. Review recursion and compare with bubble sort.

Recursive Trace

For {38,27,43,3,9,82,10}, the conceptual recursion tree is:

[38 27 43 3 9 82 10]
├─ [38 27 43]       → [27 38 43]
│  ├─ [38]          → [38]
│  └─ [27 43]       → [27 43]
└─ [3 9 82 10]      → [3 9 10 82]
   ├─ [3 9]         → [3 9]
   └─ [82 10]       → [10 82]
final merge          → [3 9 10 27 38 43 82]

Splitting does not perform the ordering work. Order is established while recursion returns and sorted child ranges are merged.

How the Merge Procedure Works

Maintain indices into the left range, right range and buffer. Copy the smaller front element, advance that range, then copy any remaining tail. Finally copy the merged buffer segment back.

while both ranges have elements
    copy the smaller front value to buffer
copy remaining left values
copy remaining right values
copy buffer segment back to values

When values are equal, taking from the left range first preserves their original relative order. That one comparison choice—<= rather than <—is central to stability.

Complete Merge Sort Program with One Reusable Buffer

#include <iostream>
#include <vector>

void merge(std::vector<int>& values, std::vector<int>& buffer,
           std::size_t left, std::size_t middle, std::size_t right) {
    std::size_t i = left, j = middle, k = left;
    while (i < middle && j < right) {
        if (values[i] <= values[j]) buffer[k++] = values[i++];
        else                         buffer[k++] = values[j++];
    }
    while (i < middle) buffer[k++] = values[i++];
    while (j < right)  buffer[k++] = values[j++];
    for (std::size_t p = left; p < right; ++p) values[p] = buffer[p];
}

void merge_sort_range(std::vector<int>& values,
                      std::vector<int>& buffer,
                      std::size_t left, std::size_t right) {
    if (right - left < 2) return;
    const std::size_t middle = left + (right - left) / 2;
    merge_sort_range(values, buffer, left, middle);
    merge_sort_range(values, buffer, middle, right);
    merge(values, buffer, left, middle, right);
}

void merge_sort(std::vector<int>& values) {
    std::vector<int> buffer(values.size());
    merge_sort_range(values, buffer, 0, values.size());
}

int main() {
    std::vector<int> values{38, 27, 43, 3, 9, 82, 10};
    merge_sort(values);
    std::cout << "Sorted:";
    for (int value : values) std::cout << ' ' << value;
    std::cout << '\n';
}

The buffer is allocated once, not at every recursive call. Midpoint calculation avoids adding two potentially large indices, and the half-open representation avoids middle+1 boundary errors.

Correctness and Stability

Use induction on range length. A range shorter than two is sorted. Assume both recursive calls correctly sort their shorter ranges. The merge procedure repeatedly selects the least unconsumed front value, so its output is ordered; every input element is copied exactly once, so the result is a permutation of the input. Therefore the parent range is sorted.

Stability matters for records sorted in stages. If two records have the same key and the left one originally appeared first, selecting left on equality retains that order. Reversing the tie choice makes this implementation unstable.

Time and Space Complexity

The recurrence is T(n)=2T(n/2)+Θ(n). An optional check can skip merging when values[middle-1] <= values[middle]; that helps ordered regions but does not alter the standard worst-case bound.

Use Cases and Algorithm Choice

Merge sort offers predictable performance and natural stability. Its sequential merge pattern is useful for external data organized in sorted runs, and linked structures can merge by relinking nodes. For an ordinary C++ vector, library algorithms are normally preferable.

See C++ algorithms and sorting/searching for production interfaces.

Common Mistakes, Testing and Practice

Test empty, one item, odd/even lengths, sorted, reverse, duplicates and negative values. Practice descending order, sorting records by key, counting comparisons, bottom-up iterative merge sort and the already-ordered merge skip.

Authoritative References

• NIST DADS: merge sort
• NIST DADS: merge operation
• C++ Working Draft: sorting operations

The divide-and-conquer definition, merge behavior and standard-library comparison were verified with these references.