Merge sort

Divide, then merge

The initial example contains ten values. The first split produces two parts of five elements; later splits need not produce equal sizes. A single element is already sorted. Once both children are sorted, their parent can be merged.

Ranges use [start, end): the left boundary is included and the right boundary is excluded. The frames show [start, middle) and [middle, end). Depth zero is the complete array. The player follows one active range rather than drawing the entire recursion tree.

Why the buffer stays sorted

Before a merge, both parts in the main row are sorted. Pointers i and j indicate their first unused elements; k indicates the next buffer position. The smaller candidate is copied to the buffer, and only its source pointer advances.

The filled buffer prefix contains the smallest elements taken so far, in sorted order. If one part runs out, the remaining tail is copied without further value comparisons. After the buffer is filled, the whole active range is copied back. The buffer contains copies: during copying back, duplicate identities can temporarily appear in the main row. This intermediate row is not the final sorted result.

Equal values retain their order

Letters a and b distinguish values that were equal in the original input. When the candidates are equal, the algorithm takes the left one: the code uses <=. Elements in the left part originally preceded those in the right part, so this tie rule preserves their relative order at every merge.

Try 2, 2, 1, 2. The final order of the three twos must remain 2a, 2b, 2c. Choosing the right candidate on equality would lose stability, although the numeric result would still be sorted.

Time, memory and counters

For n ≥ 2, this implementation takes Θ(n log n) time in the best, average and worst cases. Each recursion level copies Θ(n) elements, and there are Θ(log n) levels. Already sorted input still goes through the buffer: this version does not skip ordered merges.

The reusable buffer requires O(n) extra memory, and recursion uses O(log n) stack space. The wrapper also copies the input in O(n) time and space to leave it unchanged. Overall extra space is O(n). Empty and single-element inputs need no comparisons or merge writes.

The player counts value comparisons, buffer writes and main-array writes separately. Copying a remaining tail adds writes but no value comparisons. Pointer changes, visual buffer clearing and the initial input copy are excluded. The visualization stores O(n log n) snapshots of O(n) size, so its history has an O(n² log n) upper space bound; this is separate from the sorting algorithm's memory. Input is limited to 24 values.

JavaScript implementation

This version sorts finite numbers in ascending order and returns a new array. It uses the same split, tie rule and buffer-copy order as the player; animation events and snapshots are omitted.

function mergeSort(values) {
    const result = [...values];
    const buffer = new Array(result.length);
    function sort(start, end) {
        if (end - start <= 1) return;
        const middle = start + Math.floor((end - start) / 2);
        sort(start, middle);
        sort(middle, end);
        let left = start;
        let right = middle;
        for (let k = start; k < end; k++) {
            if (right === end ||
                (left < middle && result[left] <= result[right])) {
                buffer[k] = result[left++];
            } else {
                buffer[k] = result[right++];
            }
        }
        for (let k = start; k < end; k++) result[k] = buffer[k];
    }
    sort(0, result.length);
    return result;
}

Compare with the other sorts

Merge sort guarantees Θ(n log n) worst-case time but needs a buffer. The insertion, bubble and selection implementations shown here have Θ(n²) worst-case time and O(1) extra space when sorting in place. Their input-copying wrappers additionally use O(n) memory.

Insertion sort and bubble sort with early exit can finish sorted input in Θ(n); this merge sort still takes Θ(n log n). Selection sort takes Θ(n²) time regardless of input order and makes at most n − 1 swaps. Insertion, bubble and this merge sort are stable; selection sort with distant swaps is not.

Experiments in the player

Compare an ascending array with a descending one of the same length. Both are split identically and make the same number of merge writes, but their comparison counts can differ. Then try repeated values and watch the letter order. Use a single value or empty input to see the base case.

The visualization uses AlgiViz's scene and playback APIs. The two-row layout and merge events are implemented on this website.

Video walkthrough