Merge Sort Algorithm: Complete Guide with Rust and Go

Merge sort is a divide-and-conquer algorithm that splits an array into halves, sorts those halves recursively, and combines them with a linear-time merge operation.

For this input:

[13, 46, 24, 52, 20, 9]

the high-level process is:

divide: [13, 46, 24] + [52, 20, 9]
sort:   [13, 24, 46] + [9, 20, 52]
merge:  [9, 13, 20, 24, 46, 52]

Unlike selection sort, bubble sort, and insertion sort, merge sort guarantees O(n log n) time even when the array begins in reverse order. The trade-off for an ordinary array implementation is O(n) auxiliary storage.

This fourth article in the Sorting Algorithms series explains the recursive structure, the merge invariant, stability, memory allocation, and production trade-offs, with complete implementations in Rust and Go.

What Is Merge Sort?

Merge sort has three conceptual steps:

1. Divide: Split the current range near its midpoint.
2. Conquer: Recursively sort the left and right halves.
3. Combine: Merge the two sorted halves into one sorted range.

The base case is a range containing zero or one element. Such a range is already sorted.

merge_sort(range):
    if range has fewer than 2 elements:
        return

    divide range into left and right halves
    merge_sort(left)
    merge_sort(right)
    merge(left, right)

The important insight is that merging two sorted sequences is easier than sorting one arbitrary sequence. Their smallest remaining elements are always at their current front positions, so one comparison decides which value comes next.

How the Merge Step Works

Suppose recursion has already produced two sorted halves:

left:  [13, 24, 46]
right: [9, 20, 52]

Maintain one pointer for each half:

i -> next unused value in left
j -> next unused value in right

Compare the pointed values and copy the smaller one into the output:

13 vs 9  -> copy 9
13 vs 20 -> copy 13
24 vs 20 -> copy 20
24 vs 52 -> copy 24
46 vs 52 -> copy 46
right remains -> copy 52

The merged result is:

[9, 13, 20, 24, 46, 52]

Each value is copied exactly once during this merge, so merging a total of n values takes O(n) time.

Merge Sort Pseudocode

The range uses a half-open interval [start, end): start is included and end is excluded.

merge_sort(array, buffer, start, end):
    if end - start <= 1:
        return

    middle = start + (end - start) / 2

    merge_sort(array, buffer, start, middle)
    merge_sort(array, buffer, middle, end)
    merge(array, buffer, start, middle, end)

The merge operation is:

copy array[start..end] into buffer[start..end]

left = start
right = middle

for output from start to end - 1:
    if left half is exhausted:
        copy buffer[right]
        right = right + 1
    else if right half is exhausted:
        copy buffer[left]
        left = left + 1
    else if buffer[left] <= buffer[right]:
        copy buffer[left]
        left = left + 1
    else:
        copy buffer[right]
        right = right + 1

Allocating one buffer for the complete sort is important. Allocating fresh left and right arrays inside every recursive call creates avoidable allocation and copying overhead.

Complete Merge Sort Dry Run

Sort:

[13, 46, 24, 52, 20, 9]

Divide the array

[13, 46, 24, 52, 20, 9]
                         /                       \
                [13, 46, 24]                 [52, 20, 9]
                /          \                 /          \
             [13]       [46, 24]          [52]       [20, 9]
                         /    \                        /    \
                       [46]  [24]                    [20]  [9]

Every leaf contains one element and is therefore sorted.

Merge the left half

[46] + [24]       -> [24, 46]
[13] + [24, 46]   -> [13, 24, 46]

Merge the right half

[20] + [9]        -> [9, 20]
[52] + [9, 20]    -> [9, 20, 52]

Merge both sorted halves

[13, 24, 46] + [9, 20, 52]
-> [9, 13, 20, 24, 46, 52]

The recursion does not directly move values into final positions while dividing. All ordering happens during the merge operations on the way back up the recursion tree.

Why Merge Sort Is Correct

Correctness has two parts: the merge operation and the recursive algorithm.

Merge invariant

Before each output position is written:

• The output prefix contains the smallest consumed values from both halves.
• That prefix is sorted.
• The left and right pointers identify the smallest unused value in their respective halves.

Choosing the smaller front value therefore appends the smallest value not yet copied. The invariant remains true. When either half is exhausted, the other half's remaining values are already sorted and can be copied in order.

Cornell's merge sort notes express the same contract: if both input ranges are sorted, merge places their union into sorted order in linear time.

Recursive correctness

Use strong induction on the range length:

1. Base case: A range of length zero or one is sorted.
2. Inductive hypothesis: Assume merge sort correctly sorts every shorter range.
3. Inductive step: Both halves are shorter, so recursive calls sort them. The correct merge operation then combines them into one sorted range containing exactly the original values.

Therefore merge sort correctly sorts ranges of every finite length.

Merge Sort in Rust

This implementation allocates one reusable buffer and sorts the input slice in place with respect to its public API:

pub fn merge_sort<T: Ord + Clone>(values: &mut [T]) {
    let len = values.len();
    if len < 2 {
        return;
    }

    let mut buffer = values.to_vec();
    sort_range(values, &mut buffer, 0, len);
}

fn sort_range<T: Ord + Clone>(
    values: &mut [T],
    buffer: &mut [T],
    start: usize,
    end: usize,
) {
    if end - start <= 1 {
        return;
    }

    let middle = start + (end - start) / 2;
    sort_range(values, buffer, start, middle);
    sort_range(values, buffer, middle, end);
    merge(values, buffer, start, middle, end);
}

fn merge<T: Ord + Clone>(
    values: &mut [T],
    buffer: &mut [T],
    start: usize,
    middle: usize,
    end: usize,
) {
    buffer[start..end].clone_from_slice(&values[start..end]);

    let mut left = start;
    let mut right = middle;

    for output in &mut values[start..end] {
        if left >= middle {
            *output = buffer[right].clone();
            right += 1;
        } else if right >= end || buffer[left] <= buffer[right] {
            *output = buffer[left].clone();
            left += 1;
        } else {
            *output = buffer[right].clone();
            right += 1;
        }
    }
}

fn main() {
    let mut numbers = [13, 46, 24, 52, 20, 9];
    merge_sort(&mut numbers);
    println!("{numbers:?}");
}

#[cfg(test)]
mod tests {
    use super::merge_sort;

    #[test]
    fn sorts_integers() {
        let mut values = [13, 46, 24, 52, 20, 9];
        merge_sort(&mut values);
        assert_eq!(values, [9, 13, 20, 24, 46, 52]);
    }

    #[test]
    fn handles_empty_and_duplicate_values() {
        let mut empty: [i32; 0] = [];
        merge_sort(&mut empty);
        assert_eq!(empty, []);

        let mut duplicates = [4, 2, 4, 1, 2];
        merge_sort(&mut duplicates);
        assert_eq!(duplicates, [1, 2, 2, 4, 4]);
    }
}

The Clone bound allows values to be copied safely between the input and auxiliary slices. No unsafe memory operations are required. The comparison uses <=, so an equal value from the left half is emitted first and stability is preserved.

Merge Sort in Go

The Go implementation also allocates one reusable buffer:

package main

import "fmt"

type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 | ~string
}

func MergeSort[T Ordered](values []T) {
	if len(values) < 2 {
		return
	}

	buffer := make([]T, len(values))
	mergeSortRange(values, buffer, 0, len(values))
}

func mergeSortRange[T Ordered](values, buffer []T, start, end int) {
	if end-start <= 1 {
		return
	}

	middle := start + (end-start)/2
	mergeSortRange(values, buffer, start, middle)
	mergeSortRange(values, buffer, middle, end)
	merge(values, buffer, start, middle, end)
}

func merge[T Ordered](values, buffer []T, start, middle, end int) {
	copy(buffer[start:end], values[start:end])

	left, right := start, middle
	for output := start; output < end; output++ {
		if left >= middle {
			values[output] = buffer[right]
			right++
		} else if right >= end || buffer[left] <= buffer[right] {
			values[output] = buffer[left]
			left++
		} else {
			values[output] = buffer[right]
			right++
		}
	}
}

func main() {
	numbers := []int{13, 46, 24, 52, 20, 9}
	MergeSort(numbers)
	fmt.Println(numbers)
}

A table-driven test verifies important input shapes:

package main

import (
	"reflect"
	"testing"
)

func TestMergeSort(t *testing.T) {
	tests := []struct {
		name  string
		input []int
		want  []int
	}{
		{"empty", []int{}, []int{}},
		{"one value", []int{7}, []int{7}},
		{"already sorted", []int{1, 2, 3}, []int{1, 2, 3}},
		{"reverse order", []int{3, 2, 1}, []int{1, 2, 3}},
		{"duplicates", []int{4, 2, 4, 1}, []int{1, 2, 4, 4}},
	}

	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {
			MergeSort(test.input)
			if !reflect.DeepEqual(test.input, test.want) {
				t.Fatalf("got %v, want %v", test.input, test.want)
			}
		})
	}
}

For production code, use the language's standard sorting facilities unless you specifically need to implement or customize merge sort. Go's slices.SortStableFunc provides stable custom ordering, while Rust's slice::sort is stable and designed for general use.

Merge Sort Complexity Analysis

Standard top-down merge sort has predictable performance:

Princeton's Merge API documentation gives the same Θ(n log n) time, Θ(n) extra-memory, and stable-sorting guarantees for top-down merge sort.

Deriving the recurrence

For an input of size n:

• Two recursive calls sort ranges of about n / 2.
• One merge processes n values.

The recurrence is:

T(n) = 2T(n / 2) + O(n)

The recursion tree has log₂ n division levels. Across each level, all subproblems contain a total of n elements, so that level performs O(n) merge work:

O(n) work per level × O(log n) levels
= O(n log n)

The recursion stack is O(log n), not O(n), because the program completes one branch before returning to process another. The O(n) auxiliary buffer dominates total additional space.

Is Merge Sort Stable?

Merge sort is stable only when the merge implementation handles equal keys correctly.

Suppose the left and right halves contain:

left:  [(2, A), (4, B)]
right: [(2, C), (3, D)]

The original left-half record (2, A) appeared before (2, C). When their keys tie, choosing the left value first produces:

[(2, A), (2, C), (3, D), (4, B)]

Their relative order is preserved. This condition is stable:

left <= right -> choose left

This condition is not stable:

left < right -> choose left, otherwise choose right

In the second version, a tie incorrectly chooses the right record first.

Why Merge Sort Uses O(n) Extra Space

During an array merge, writing a selected value directly into the original range can overwrite a value that has not yet been compared. A temporary buffer preserves the source values while the destination is rewritten.

Allocating one buffer of length n gives:

auxiliary buffer: O(n)
recursion stack:  O(log n)
total:            O(n)

Creating new left and right arrays at every call can increase allocation pressure even though peak asymptotic usage remains O(n) with disciplined recursion. Reusing one buffer is more predictable.

In-place stable merging is possible, but the algorithms are more complex and can require additional rotations, searches, or movement. “In-place merge sort” is not a drop-in improvement; evaluate its constant factors and implementation risk.

Bottom-Up Merge Sort

Bottom-up merge sort removes recursion. Begin with sorted runs of width one, then merge adjacent runs of width two, four, eight, and so on:

width 1: [13] [46] [24] [52] [20] [9]
width 2: [13,46] [24,52] [9,20]
width 4: [13,24,46,52] [9,20]
width 8: [9,13,20,24,46,52]

Pseudocode:

width = 1
while width < n:
    for start from 0 to n in steps of 2 * width:
        middle = min(start + width, n)
        end = min(start + 2 * width, n)
        merge(start, middle, end)
    width = 2 * width

It retains O(n log n) time and O(n) buffer space while avoiding recursive calls. Careful boundary handling is required when the final run is shorter than width.

Merge Sort for Linked Lists and External Data

Merge sort is especially well suited to linked lists. Splitting can use slow and fast pointers, and merging can relink nodes rather than shifting array elements. The algorithm can use much less additional element storage than its array version.

It is also the foundation of external merge sort for data larger than memory:

1. Read chunks that fit in memory.
2. Sort each chunk and write it as a run to storage.
3. Merge multiple sorted runs sequentially.

Sequential reading and writing works well with disks and object storage. This is one reason merge-based strategies appear in databases, data-processing systems, and large file-sorting workflows.

Practical Merge Sort Optimizations

Skip an already ordered merge

After sorting both halves, test the boundary:

if array[middle - 1] <= array[middle]:
    return

If true, every left value is already no greater than every right value. The merge can be skipped. This improves nearly sorted inputs and can produce O(n) best-case behavior in an optimized implementation, although standard merge sort remains O(n log n).

Use insertion sort for small ranges

Recursive setup and buffer copying have fixed overhead. Hybrid implementations often switch to insertion sort below a measured cutoff, then merge the resulting runs.

Do not copy a universal threshold. Benchmark representative element types, comparators, and hardware.

Reuse the auxiliary buffer

Allocate it once at the top level. Repeated allocations make runtime noisier and increase garbage-collector or allocator work.

Parallelize large independent halves

The two recursive halves are independent until merging. Large inputs can sort them concurrently, but task creation and synchronization cost mean small subproblems should remain sequential.

Common Merge Sort Mistakes

Missing the base case

Stop when the range length is at most one. Without this condition, recursion never terminates correctly.

Inconsistent range boundaries

Choose [start, end) or inclusive endpoints and use that convention everywhere. Mixing them causes missing elements and out-of-bounds access.

Breaking stability on equal values

Choose from the left half when keys are equal.

Forgetting remaining values

When one half is exhausted, copy every value remaining in the other half.

Allocating temporary arrays recursively

Prefer one reusable buffer unless simplicity is the explicit goal.

Claiming standard array merge sort is in place

The normal implementation uses O(n) auxiliary element storage. Recursion space alone is not the complete space cost.

Overflow-prone midpoint calculation

Use:

middle = start + (end - start) / 2

instead of (start + end) / 2 in languages where index addition can overflow.

Merge Sort Compared with Earlier Algorithms

Merge sort is the first algorithm in this series with a worst-case O(n log n) guarantee. That makes it appropriate for much larger inputs, especially when stability and predictable performance matter. Insertion sort can still win on tiny ranges, which is why the two algorithms are often combined.

When Should You Use Merge Sort?

Merge sort is a strong choice when:

• Worst-case O(n log n) time is required.
• Stable ordering of equal records matters.
• Sequential access is preferable.
• You are sorting linked lists.
• Data must be sorted externally in multiple runs.
• Independent halves can be processed in parallel.

Consider another strategy when:

• O(n) auxiliary array storage is unacceptable.
• The input is tiny or nearly sorted and insertion sort is sufficient.
• Cache-local in-place array performance matters more than stability.
• The language's tested standard sorter already meets the requirement.

The Bottom Line

Merge sort separates sorting into two manageable operations:

divide into halves -> sort each half -> merge sorted halves

Its recurrence T(n) = 2T(n / 2) + O(n) produces O(n log n) time in the best, average, and worst cases for the standard implementation. It is stable when equal values come from the left half first, and its normal array implementation uses O(n) auxiliary buffer space plus an O(log n) recursion stack.

The merge invariant is the key idea: the output always contains the smallest values consumed so far in sorted order. Once that operation is correct, recursion builds a complete sorted result from single-element ranges.

Continue with the complete Quick Sort Algorithm guide, then explore the Sorting Algorithms category for more step-by-step tutorials and Rust and Go implementations.