C++UCS301
Sorting AlgorithmsC++17

Merge Sort

Merge sort recursively divides the input, sorts both halves, and linearly merges the sorted results.

What to understand

  • Divide and conquer
  • Linear merge
  • Recurrence T(n)=2T(n/2)+O(n)
  • External sorting

Remember this

  1. 1Guaranteed O(n log n)
  2. 2Stable with careful merging
  3. 3Array version needs O(n) extra space
  4. 4Natural for linked lists and files

Detailed notes

Merge sort recursively reduces the problem to single-element sorted ranges. Merging compares the front unconsumed values of two sorted ranges, so each merge level processes every element once.

There are log n levels and O(n) work per level, giving Θ(n log n) in every case. Arrays require an auxiliary buffer; linked lists can merge by relinking nodes.

How it works

  1. 1Split the half-open range at its midpoint.
  2. 2Recursively sort both halves.
  3. 3Merge by taking the smaller front value.
  4. 4Copy remaining tails and place the merged result back.

Worked trace

Merge two sorted halves

Left [2,7,9], right [1,5,8]
  1. 1Compare 2 and 1; take 1.
  2. 2Compare 2 and 5; take 2.
  3. 3Compare 7 and 5; take 5.
  4. 4Compare 7 and 8; take 7, then 8, then remaining 9.
Result: [1,2,5,7,8,9] · linear merge

Where it is used

  • Stable record sorting
  • Linked-list sorting
  • External run merging and parallel sorting

Common mistakes

  • Mixing inclusive and half-open bounds
  • Choosing the right half on equality and losing stability
  • Allocating a fresh large buffer at every recursion level

Complexity analysis

OperationBestAverageWorstExtra space
SortO(n log n)O(n log n)O(n log n)O(n)

C++ implementation

C++17 reference
main.cpp

Stable merge sort

Taking from the left on equality preserves the original order of equal values.

void mergeSort(vector<int>& a, int left, int right) {
    if (right - left <= 1) return;
    int mid = left + (right - left) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid, right);

    vector<int> merged;
    int i = left, j = mid;
    while (i < mid && j < right)
        merged.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
    while (i < mid) merged.push_back(a[i++]);
    while (j < right) merged.push_back(a[j++]);
    copy(merged.begin(), merged.end(), a.begin() + left);
}
14 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.