Merge Sort

Merge sort divides a sequence into halves, sorts each half, then merges their sorted outputs. The merge step uses the fact that the smallest remaining element of two sorted sequences must be at one of their fronts. Its predictable O(n log n) time and stable tie handling make it useful when worst-case guarantees or equal-key order matter. This lesson uses top-down recursion with one reusable buffer.

Prerequisites: Recursion; Introduction to Sorting.

Build the idea

1. 1. Define half-open subproblems

   mergeSort(a,buffer,l,r) sorts indices l through r−1. A range of length zero or one is already sorted. Splitting at l+(r−l)/2 gives [l,mid) and [mid,r), without overlapping or omitting an element. Both ranges are smaller when length exceeds one, ensuring recursive termination.

2. 2. Assume the halves are sorted only after recursion

   First recursively sort both halves; then compare their current front values with pointers i and j. The smaller front is the smallest element not yet written, so copy it to buffer[k] and advance its pointer. When one half empties, append all remaining values of the other; they are already ordered.

3. 3. Preserve equivalent-key order

   On equality choose from the LEFT half, using <= in the merge selection. This is different from a sort comparator: here <= deliberately chooses which tied record to copy. Since recursive halves are themselves stable and original left positions preceded right positions, this rule preserves the original relative order of equivalent keys.

4. 4. Trace [4,1,3,2]

   The halves [4,1] and [3,2] become [1,4] and [2,3]. Merging chooses 1, then 2, then 3, then the remaining 4. At each point buffer contains the smallest processed output prefix. Finally copy buffer[l..r) back into a so the caller sees the sorted range. A single n-element buffer is reused across every call, avoiding allocation per merge.

5. 5. Derive the cost

   There are O(log n) split levels. At each level, all merges together scan and copy O(n) elements. Therefore total time is O(n log n), including already sorted input in this straightforward implementation. The buffer has n entries and recursion depth is O(log n). This array version is not in-place in the strict constant-extra-storage sense; linked-list merging can have different storage behavior.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
void mergeSort(std::vector<int>&a,std::vector<int>&buffer,int l,int r){
    if(r-l<=1){
        return; // Half-open [l,r), including empty ranges.
    }
    int mid=l+(r-l)/2;
    mergeSort(a,buffer,l,mid);
    mergeSort(a,buffer,mid,r);
    int i=l,j=mid,k=l;
    while(i<mid&&j<r){
        buffer[k++]=a[i]<=a[j]?a[i++]:a[j++];
    }
    while(i<mid){
        buffer[k++]=a[i++];
    }
    while(j<r){
        buffer[k++]=a[j++];
    }
    for(int p=l;p<r;++p){
        a[p]=buffer[p];
    }
}
int main(){
    int n;
    std::cin>>n;
    std::vector<int>a(n),buffer(n);
    for(int&x:a){
        std::cin>>x;
    }
    mergeSort(a,buffer,0,n);
    for(int i=0;i<n;++i){
        std::cout<<a[i]<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
}

Complexity analysis

O(n log(n+1)) time, O(n) auxiliary buffer and O(log(n+1)) recursion stack, hence O(n) auxiliary space overall. The input itself is O(n). These guarantees do not depend on pivot choices or input order. n≤200000 is suitable for this teaching implementation.

Example input and output

Read n (0..200000), then n int values. Print the ascending sequence; print a blank line when empty.

Input

4
4 1 3 2

Output

1 2 3 4

Sorted halves [1,4] and [2,3] merge by repeatedly taking the smaller front.

Practical applications

Use for stable predictable sorting, inversion counting extensions and external merge workflows. std::sort usually uses less extra memory and need not be stable. std::stable_sort is convenient when writing your own merge is unnecessary; its exact guarantees were described in the sorting introduction.

Check your understanding

What tie rule makes the merge stable?

Put it into practice

Modify the merge to count pairs i<j with a[i]>a[j].