Merge Sort — Top Down and Bottom Up for Arrays and Linked Lists

Merge sort is one of the most dependable general-purpose sorting algorithms. It follows a divide-and-conquer approach, is practical to reason about, and guarantees O(n log n) running time regardless of the input order.

This guide starts with the fundamental merge operation, builds top-down and bottom-up array implementations, and then applies the same idea to a singly linked list.

This article was originally published on Medium on 29 May 2022 and has been revised for DeftMove.

What is merge sort?

Merge sort is a stable, comparison-based sorting algorithm. It repeatedly divides an input into smaller ranges, sorts those ranges, and combines them with a merge operation.

The top-down algorithm has three steps:

1. Split the input approximately in half.
2. Sort each half by applying the same process recursively.
3. Merge the two sorted halves into one sorted range.

A range containing zero or one value is already sorted, so it forms the recursion’s base case. The merge step then rebuilds progressively larger sorted ranges.

Unlike quick sort, merge sort does not rely on choosing a good pivot. Its partitions are always close to equal, giving it predictable performance.

Merging two sorted arrays

Before sorting a complete input, it helps to isolate the operation at the heart of the algorithm.

Suppose we have these two sorted arrays:

left  = [2, 11, 18, 20, 22]
right = [4, 9, 19, 25]

Create an output array large enough to hold both inputs. Use i to track the next value in left, j for right, and k for the next output position.

The process is straightforward:

1. Compare left[i] with right[j].
2. Copy the smaller value to output[k].
3. Advance k and the pointer belonging to the chosen value.
4. Continue until one input has no values left.
5. Copy the remaining values from the other input.

The completed output is:

[2, 4, 9, 11, 18, 19, 20, 22, 25]

If the arrays contain n and m values, the merge takes O(n + m) time because each value is copied exactly once. Creating a separate result requires O(n + m) storage.

To keep the merge stable, take the value from the left input when the two candidates are equal. In code, that means comparing with <=, not <.

Merging adjacent sorted halves

An array merge sort usually does not create two physical arrays for every split. Instead, it treats adjacent ranges inside one array as the two sorted inputs.

Consider:

[2, 5, 8, 12 | 3, 6, 7, 11]

The original diagrams use inclusive boundaries: low and mid define the left range, while mid + 1 through high define the right range.

The implementations later in this article use equivalent half-open ranges: [start, middle) and [middle, end). Half-open ranges make the length end - start and avoid repeatedly adding or subtracting one at the boundaries.

For the inclusive diagram, initialize i = low, j = mid + 1, and k = low. The same two-pointer merge writes into a reusable auxiliary array, then copies the completed range back into the source.

The merge logic for two separate arrays and two adjacent ranges is almost identical. Only the boundaries and the destination indexes change.

Top-down merge sort

Top-down merge sort begins with the whole input and keeps dividing each range in half. Once it reaches one-value ranges, the merge phase starts.

For a half-open range [start, end):

1. Return when end - start <= 1.
2. Calculate middle = start + (end - start) / 2.
3. Sort [start, middle).
4. Sort [middle, end).
5. Merge the two sorted ranges.

These implementations allocate one reusable buffer for the complete sort rather than allocating new left and right arrays during every recursive call.

using System;

public static class MergeSort
{
    public static void Sort(int[] values)
    {
        ArgumentNullException.ThrowIfNull(values);

        int[] buffer = new int[values.Length];
        SortRange(values, buffer, 0, values.Length);
    }

    private static void SortRange(
        int[] values,
        int[] buffer,
        int start,
        int end)
    {
        if (end - start <= 1)
            return;

        int middle = start + (end - start) / 2;
        SortRange(values, buffer, start, middle);
        SortRange(values, buffer, middle, end);
        Merge(values, buffer, start, middle, end);
    }

    private static void Merge(
        int[] values,
        int[] buffer,
        int start,
        int middle,
        int end)
    {
        int left = start;
        int right = middle;
        int write = start;

        while (left < middle && right < end)
        {
            if (values[left] <= values[right])
                buffer[write++] = values[left++];
            else
                buffer[write++] = values[right++];
        }

        while (left < middle)
            buffer[write++] = values[left++];

        while (right < end)
            buffer[write++] = values[right++];

        Array.Copy(buffer, start, values, start, end - start);
    }
}

def merge_sort(values: list[int]) -> None:
    buffer = [0] * len(values)

    def sort_range(start: int, end: int) -> None:
        if end - start <= 1:
            return

        middle = start + (end - start) // 2
        sort_range(start, middle)
        sort_range(middle, end)
        merge(start, middle, end)

    def merge(start: int, middle: int, end: int) -> None:
        left = start
        right = middle

        for write in range(start, end):
            if left < middle and (
                right >= end or values[left] <= values[right]
            ):
                buffer[write] = values[left]
                left += 1
            else:
                buffer[write] = values[right]
                right += 1

        for index in range(start, end):
            values[index] = buffer[index]

    sort_range(0, len(values))

package sorting

func MergeSort(values []int) {
	buffer := make([]int, len(values))

	var sortRange func(start, end int)
	sortRange = func(start, end int) {
		if end-start <= 1 {
			return
		}

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

	sortRange(0, len(values))
}

func merge(values, buffer []int, start, middle, end int) {
	left := start
	right := middle
	write := start

	for left < middle && right < end {
		if values[left] <= values[right] {
			buffer[write] = values[left]
			left++
		} else {
			buffer[write] = values[right]
			right++
		}
		write++
	}

	for left < middle {
		buffer[write] = values[left]
		left++
		write++
	}

	for right < end {
		buffer[write] = values[right]
		right++
		write++
	}

	copy(values[start:end], buffer[start:end])
}

All three versions mutate the supplied collection from the caller’s perspective. They handle empty inputs, one-value inputs, duplicates, and negative values, and they preserve stability by choosing from the left range when values compare equal.

Bottom-up merge sort

Bottom-up merge sort performs the same merges without recursion. It starts by treating every individual value as a sorted run of width one.

It then performs a sequence of passes:

width 1: merge neighbouring one-value runs
width 2: merge neighbouring two-value runs
width 4: merge neighbouring four-value runs
...

Each pass must also merge a final partial run when the input length is not a power of two. Skipping that trailing range is a common implementation bug.

Bottom-up merge sort still uses O(n) auxiliary array storage. What it removes is the O(log n) recursive call stack.

Merge sort for linked lists

Merge sort is particularly natural for linked lists. It does not need random access, and the merge can relink existing nodes instead of copying values into an array-sized buffer.

A top-down linked-list implementation follows three steps:

1. Find the midpoint with a slow pointer that moves one node and a fast pointer that moves two.
2. Disconnect the list at the midpoint and recursively sort both halves.
3. Merge the two sorted lists by changing their Next links.

The midpoint scan and merge are both linear in the number of nodes they visit. Because every recursion level processes O(n) nodes and there are O(log n) levels, the complete sort takes O(n log n) time.

The following tabs compare the iterative array version with the recursive linked-list version:

using System;

public static class BottomUpMergeSort
{
    public static void Sort(int[] values)
    {
        ArgumentNullException.ThrowIfNull(values);

        int[] buffer = new int[values.Length];

        for (int width = 1; width < values.Length; width *= 2)
        {
            for (
                long blockStart = 0;
                blockStart < values.LongLength - width;
                blockStart += 2L * width)
            {
                int start = (int)blockStart;
                int middle = start + width;
                int end = (int)Math.Min(
                    blockStart + 2L * width,
                    values.LongLength);
                Merge(values, buffer, start, middle, end);
            }

            // Prevent integer overflow after the final useful pass.
            if (width > values.Length / 2)
                break;
        }
    }

    private static void Merge(
        int[] values,
        int[] buffer,
        int start,
        int middle,
        int end)
    {
        int left = start;
        int right = middle;
        int write = start;

        while (left < middle && right < end)
        {
            if (values[left] <= values[right])
                buffer[write++] = values[left++];
            else
                buffer[write++] = values[right++];
        }

        while (left < middle)
            buffer[write++] = values[left++];

        while (right < end)
            buffer[write++] = values[right++];

        Array.Copy(buffer, start, values, start, end - start);
    }
}

public sealed class Node
{
    public Node(int value) => Value = value;

    public int Value { get; }
    public Node? Next { get; set; }
}

public static class LinkedListMergeSort
{
    public static Node? Sort(Node? head)
    {
        if (head is null || head.Next is null)
            return head;

        Node secondHalf = Split(head);
        Node? left = Sort(head);
        Node? right = Sort(secondHalf);

        return Merge(left, right);
    }

    private static Node Split(Node head)
    {
        Node slow = head;
        Node? fast = head.Next;

        while (fast?.Next is not null)
        {
            slow = slow.Next!;
            fast = fast.Next.Next;
        }

        Node secondHalf = slow.Next!;
        slow.Next = null;
        return secondHalf;
    }

    private static Node? Merge(Node? left, Node? right)
    {
        if (left is null)
            return right;

        if (right is null)
            return left;

        Node head;

        if (left.Value <= right.Value)
        {
            head = left;
            left = left.Next;
        }
        else
        {
            head = right;
            right = right.Next;
        }

        Node tail = head;

        while (left is not null && right is not null)
        {
            if (left.Value <= right.Value)
            {
                tail.Next = left;
                left = left.Next;
            }
            else
            {
                tail.Next = right;
                right = right.Next;
            }

            tail = tail.Next;
        }

        tail.Next = left ?? right;
        return head;
    }
}

The linked-list merge reuses the original nodes. Its merge workspace is O(1), while the top-down recursion consumes O(log n) call-stack space. A bottom-up linked-list implementation can remove that recursion stack as well.

Time complexity

Merge sort always divides the input into approximately equal halves:

• The recursion tree or bottom-up pass sequence has O(log n) levels.
• Across each level, merging processes a total of O(n) values.
• Multiplying those quantities gives O(n log n).

Unlike basic quick sort, the input’s existing order does not produce an O(n²) case.

An optional early-out check can skip a merge when the largest value in the left range is already no greater than the smallest value in the right range. That optimization helps ordered data, but it is not part of the basic versions shown here.

Space complexity

For the implementations in this guide:

The O(n) array buffer is reusable across every merge. It should not be multiplied by the O(log n) number of levels when calculating peak auxiliary space. An implementation that repeatedly creates temporary arrays may perform O(n log n) total allocation over the whole run, but it still does not need O(n log n) simultaneously live storage.

Why merge sort is stable

Suppose two records have equal sort keys, and the left record appeared earlier in the original input. During the merge, choosing the left value when the keys are equal preserves that order:

left value <= right value

That one comparison makes these implementations stable. Choosing from the right on equality would reverse some equal-key records and lose stability.

Stability is valuable when data has already been sorted by another field. For example, a stable department sort can preserve the existing name order among employees in the same department.

Common mistakes

• Mixing inclusive and half-open boundaries.
• Forgetting the zero- or one-value base case.
• Merging before both source ranges have been sorted.
• Failing to copy a completed array merge back to the source.
• Choosing the right value on equality and accidentally losing stability.
• Allocating fresh temporary arrays for every merge instead of reusing one buffer.
• Ignoring a partial trailing run in bottom-up merge sort.
• Dereferencing head.Next without handling an empty linked list.

Frequently asked questions

Is merge sort adaptive?

The conventional top-down and bottom-up algorithms are not adaptive: they perform the same split-and-merge structure even when the input is already sorted. Natural merge sort is an adaptive variation that detects and combines existing ordered runs.

Is merge sort in place?

The standard array implementation is not in place because it needs an O(n) auxiliary buffer. More specialized in-place array merges exist, but they are substantially more complex.

Linked-list merge sort is different: it can merge by relinking existing nodes with O(1) merge workspace. A recursive version still uses its O(log n) call stack.

Is merge sort suitable for linked lists?

Yes. Its sequential scans match linked-list access well, and merging does not require random indexing. Insertion sort can also work well for small or nearly sorted lists, while array-oriented algorithms often lose their usual advantages on linked nodes.

When should I use merge sort?

Use it when you need:

• a guaranteed O(n log n) running time;
• stable ordering for equal keys;
• sequential access, as with linked lists or external data;
• predictable behaviour across different input shapes.

For small in-memory arrays where auxiliary space is expensive, another algorithm or a hybrid standard-library sort may be a better fit.

Advantages and disadvantages

Merge sort’s main advantages are:

• consistent O(n log n) performance;
• natural stability;
• a good fit for linked lists and sequential data;
• a structure that can be parallelized or adapted to external sorting.

Its main costs are:

• O(n) auxiliary storage for straightforward array implementations;
• copying values between the source and buffer;
• recursion overhead in the top-down form;
• no automatic benefit from ordered input in the conventional algorithm.

Conclusion

Merge sort grows from one simple operation: merge two sorted ranges by repeatedly taking their smallest unconsumed value. Top-down merge sort reaches those ranges by splitting recursively; bottom-up merge sort builds them through width-doubling passes; linked-list merge sort uses the same invariant while relinking nodes.

The key implementation choices are precise range boundaries, a reusable array buffer, left-first handling of equal values, and correct treatment of partial runs. With those details in place, merge sort remains stable, predictable, and O(n log n) across very different input shapes.