Merge sort

Sorting Visual walkthrough

At a glance

Merge sort divides an array into smaller pieces, sorts each piece and merges the results. Its running time stays predictable as the input grows.

Property	What to remember
Typical time	O(n log n)
Extra memory	O(n)
Stable?	Yes, with the implementation shown
Good choice when	You need predictable performance on large inputs

Watch it work

The bars show the values and their current positions. Use Next to inspect one action, or Play to follow the whole sequence. You can enter your own numbers and compare what happens with a nearly sorted or reversed list.

Interactive walkthrough0 / 0

Explanation modeChallengePracticeGuidedExplain each step yourself, then reveal the answer when ready.

What is happening?

Explain the current action in your own words.

Reveal explanation

Why are we doing this?

Why is this step necessary?

Reveal explanation

Coming next

Predict what will happen next.

Reveal explanation

Step

0

PreviousPlayNextResetShuffle

Comparisons 0Writes 0Events 0

Custom values (4 to 10 integers from 1 to 99)

Use values

Purple: compared or moved | Green: completed portion | Orange: active work area

What the colors mean

Purple marks comparisons or movement, orange shows the active part of the array, and green highlights sections that the visualizer has completed. The animation counts individual comparisons and assignments in its teaching model, not CPU instructions or elapsed time.

Splitting and merging at a glance

Notice that the recursive split creates single-element ranges, while the merge phase produces progressively larger sorted runs.

Approach explained step by step

1. Find the middle. Divide the current range into a left half and a right half.
2. Sort each half. Apply the same procedure recursively, stopping at ranges of one element.
3. Create a temporary buffer. During the merge, the two halves are already sorted, so their first unconsumed elements are enough to decide the next output.
4. Compare the heads. Take the smaller of the two available values and append it to the buffer. When values are equal, taking from the left keeps the algorithm stable.
5. Copy the remainder. Once one half runs out, append every remaining element of the other half.
6. Write the merged sequence back. The entire range is now sorted. Repeat as recursive calls return.

Trace a small input by hand

For [7, 3, 5], divide into [7] and [3, 5], then split the latter into [3] and [5]. Merge those into [3, 5]. Finally compare the first items of [7] and [3, 5], taking 3, then 5, then 7. The result is [3, 5, 7].

Implementations in C# and C++

C#

C# | MergeSort.cs

static void MergeSort(int[] a)
{
    int[] buffer = new int[a.Length];
    Sort(0, a.Length);

    void Sort(int start, int end)
    {
        if (end - start <= 1) return;
        int middle = start + (end - start) / 2;
        Sort(start, middle);
        Sort(middle, end);

        int left = start, right = middle;
        for (int k = start; k < end; k++)
        {
            if (right == end ||
                (left < middle && a[left] <= a[right]))
                buffer[k] = a[left++];
            else
                buffer[k] = a[right++];
        }
        Array.Copy(buffer, start, a, start, end - start);
    }
}

C++

C++ | MergeSort.cpp

#include <vector>
#include <algorithm>
void mergeSort(std::vector<int>& values) {
    if (values.size() < 2) return;
    std::vector<int> buffer(values.size());
    auto sort = [&](auto&& self, int lo, int hi) -> void {
        if (hi - lo < 2) return;
        int mid = lo + (hi - lo) / 2;
        self(self, lo, mid); self(self, mid, hi);
        std::merge(values.begin()+lo, values.begin()+mid,
                   values.begin()+mid, values.begin()+hi,
                   buffer.begin()+lo);
        std::copy(buffer.begin()+lo, buffer.begin()+hi, values.begin()+lo);
    };
    sort(sort, 0, static_cast<int>(values.size()));
}

Try a mental trace

Why is it enough to compare only the first remaining item from each sorted half? Try merging [2, 8] and [3, 7] by hand.

Complexity and trade-offs

Measure	Cost	Reason
Best case	O(n log n)	Splitting and merging still happen even when already sorted.
Average case	O(n log n)	There are logarithmically many levels of merging.
Worst case	O(n log n)	Each level visits all n items.
Auxiliary space	O(n)	The implementation uses a temporary buffer.
Stability	Stable	Taking a value from the left half on a tie preserves order.

Merge sort gives a strong worst-case bound but needs additional storage for the merge buffer. Unlike an in-place algorithm, it must allocate or reuse scratch space. It is often a good choice when stable ordering matters.

Common mistakes

• Merging halves before they have been sorted.
• Mishandling inclusive versus exclusive range boundaries. This example uses [start, end).
• Forgetting to copy remaining elements when one half runs out.
• Forgetting that the auxiliary buffer affects memory complexity.

Why the merge step works

The two input halves are already sorted by their recursive calls. The next output item must therefore be the smaller of the two front items. Once an item has been copied to the output, it never needs to move again during this merge. When one half runs out, copy the rest of the other half.

Memory trade-offs

A typical array-based merge sort requires an auxiliary buffer proportional to the input size. Reusing a single buffer across recursive calls is generally preferable to allocating fresh arrays at every merge. The recursion itself adds a logarithmic call-stack depth, but the O(n) buffer dominates the auxiliary-space bound.

Stability matters

When both front values are equal, take the item from the left half first. That maintains the relative ordering of equal keys. Stable sorting is useful when records were previously ordered by another field.

Further reading

↗External referenceInteractive Merge sort referenceExplore another visual explanation of merge sort.↗Related lessonBig O notationUnderstand how algorithmic work scales with input size.↗Related lessonTime complexityLearn how to estimate the number of operations an algorithm needs.

Compare the approaches

↗Hands-on exerciseCompare sorting approachesRun insertion sort and merge sort on the same values. Compare their steps and explain why their behavior differs.