Merge Sort

How Merge Sort Works

Merge sort follows the divide-and-conquer paradigm. It breaks a problem into smaller subproblems, solves each subproblem independently, and then combines the results. For sorting, this means dividing the array until each piece has one element (which is trivially sorted), then merging adjacent pieces in sorted order.

Step-by-step process:

Divide: Split the array into two roughly equal halves by finding the midpoint. If the array has n elements, the left half contains elements at indices 0 through mid, and the right half contains mid+1 through n-1.
Conquer: Recursively apply merge sort to each half. Continue splitting until each subarray has a single element (the base case).
Merge: Combine two sorted subarrays into one sorted array. Use two pointers, one for each subarray, and repeatedly pick the smaller of the two pointed-to elements, placing it into the result. When one subarray is exhausted, copy the remaining elements from the other.
Result: Once the recursion unwinds completely, the entire array is sorted. Each level of recursion does O(n) work across all merges at that level, and there are O(log n) levels, giving the overall O(n log n) complexity.

Merge sort's main drawback is that it requires O(n) additional memory for the temporary arrays used during merging. However, its guaranteed O(n log n) performance and stability make it an excellent choice when predictable performance matters, such as sorting linked lists or external data that does not fit in memory.

Interactive Visualization

Watch how merge sort recursively splits the array into smaller pieces and then merges them back in sorted order. Yellow bars show the left subarray, orange bars show the right subarray, and green bars are merged and sorted. Orange comparison arrows indicate which two elements are being compared during a merge.

Press Play or Step to start the visualization.

Speed No steps

Code Implementation

Below is a standard top-down merge sort implementation in three languages. The algorithm recursively splits the array, then uses a merge function to combine sorted halves.

def merge_sort(arr):
    """Top-down merge sort."""
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)


def merge(left, right):
    """Merge two sorted arrays into one sorted array."""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Append remaining elements
    result.extend(left[i:])
    result.extend(right[j:])
    return result


# Example usage
numbers = [38, 27, 43, 3, 9, 82, 10]
print("Unsorted:", numbers)
print("Sorted:  ", merge_sort(numbers))

public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;

        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
        for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }

    public static void main(String[] args) {
        int[] numbers = {38, 27, 43, 3, 9, 82, 10};
        System.out.print("Unsorted: ");
        printArray(numbers);

        mergeSort(numbers, 0, numbers.length - 1);

        System.out.print("Sorted:   ");
        printArray(numbers);
    }

    private static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) System.out.print(", ");
        }
        System.out.println();
    }
}

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;
    while (i < (int)leftArr.size() && j < (int)rightArr.size()) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    while (i < (int)leftArr.size()) arr[k++] = leftArr[i++];
    while (j < (int)rightArr.size()) arr[k++] = rightArr[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

void printArray(const vector<int>& arr) {
    for (int i = 0; i < (int)arr.size(); i++) {
        cout << arr[i];
        if (i < (int)arr.size() - 1) cout << ", ";
    }
    cout << endl;
}

int main() {
    vector<int> numbers = {38, 27, 43, 3, 9, 82, 10};
    cout << "Unsorted: ";
    printArray(numbers);

    mergeSort(numbers, 0, numbers.size() - 1);

    cout << "Sorted:   ";
    printArray(numbers);
    return 0;
}

Complexity Analysis

Merge sort has consistent O(n log n) time complexity in all cases because it always divides the array in half and always performs a linear-time merge at each level of recursion. The trade-off is O(n) extra space for the temporary arrays used during merging.

Metric	Complexity	Notes
Best Case Time	O(n log n)	Always divides and merges, even if already sorted
Average Case Time	O(n log n)	Consistent regardless of input order
Worst Case Time	O(n log n)	Guaranteed -- no pathological inputs
Space Complexity	O(n)	Requires auxiliary arrays for merging
Stable	Yes	Equal elements maintain their relative order during merge

Quiz

Test your understanding of merge sort with these questions.

Q1. What is the worst-case time complexity of merge sort?

O(n²)

O(n)

O(n log n)

O(log n)

Merge sort always divides the array in half (log n levels) and performs O(n) work at each level for merging, giving O(n log n) in all cases -- best, average, and worst.

Q2. What is the space complexity of standard merge sort?

O(1) -- it sorts in place

O(n) -- it needs auxiliary arrays for merging

O(n log n) -- one copy per recursion level

O(log n) -- only for the recursion stack

Standard merge sort requires O(n) additional space to hold the temporary left and right subarrays during the merge phase. The recursion stack adds O(log n), but the dominant term is the O(n) auxiliary space.

Q3. Is merge sort a stable sorting algorithm?

Yes, because equal elements from the left subarray are placed before those from the right

No, because the divide step may split equal elements into different halves

It depends on the pivot selection

Only when implemented iteratively (bottom-up)

Merge sort is stable because during the merge step, when two elements are equal, the element from the left subarray is always placed first. This preserves the original relative order of equal elements.

Q4. How many levels of recursion does merge sort produce for an array of 16 elements?

16

8

3

4

Each level of recursion halves the array size: 16 -> 8 -> 4 -> 2 -> 1. That is log2(16) = 4 levels of splitting. The total depth of the recursion tree is 4.

Q5. Which of the following is a key advantage of merge sort over quicksort?

Merge sort uses less memory

Merge sort guarantees O(n log n) worst-case time

Merge sort is always faster in practice

Merge sort does not require comparisons

Quicksort's worst case is O(n²) (e.g., when the pivot is always the smallest or largest element), while merge sort always runs in O(n log n) regardless of the input. This guaranteed performance is merge sort's main advantage, even though quicksort is often faster in practice due to better cache behavior and lower constant factors.

How Merge Sort Works

Interactive Visualization

Code Implementation

Complexity Analysis

Quiz

Keyboard Shortcuts