Merge Sort Algorithm O n log n Stable Sort

What is Merge Sort?

Merge sort is useful when predictable O(n log n) time and stable ordering matter more than sorting in place.

Choose it for linked lists, external sorting, and records that may be sorted by more than one key. Avoid it on tight memory budgets where the extra merge buffer is the real constraint.

The important checks are the split condition, the merge loop, and whether equal values keep their original order.

This divide-and-conquer algorithm splits input until each run has one element, then combines sorted runs with a linear merge.

Its predictable O(n log n) running time holds for best, average, and worst cases. Taking an equal value from the left run first also preserves stable ordering.

Core Idea

Merge Sort works in two major phases:

The key operation is the merge step, where two already sorted subarrays are combined efficiently.

Divide: split the array into two halves.
Conquer: recursively sort both halves.
Combine: merge the two sorted halves into one sorted array.

Why Merge Sort Is Always O(n log n)

The array is repeatedly divided in half, so the number of division levels is about log n. At each level, all elements are processed once during merging, which costs O(n).

So the total work is:

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

This is why Merge Sort has the same asymptotic running time in all cases.

Time and Space Complexity

Metric	Best	Average	Worst	Space	Stable?
Time Complexity	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Recurrence	T(n) = 2T(n/2) + O(n)	-	-
Recursion depth	O(log n)	-	-

How Merge Sort Works

Consider the array [38, 27, 43, 3, 9, 82, 10].

Final result: [3, 9, 10, 27, 38, 43, 82]

Split into [38, 27, 43, 3] and [9, 82, 10]
Split further into [38, 27], [43, 3], [9, 82], and [10]
Continue until single-element arrays remain
Merge single elements into sorted pairs
Merge sorted pairs into larger sorted subarrays
Continue until one fully sorted array remains

Merge Sort Implementation

import java.util.Arrays;

public class MergeSort {

    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);
    }

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

        int[] leftPart = new int[n1];
        int[] rightPart = new int[n2];

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

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

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

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("After:  " + Arrays.toString(arr));
    }
}

How Merge Sort Works - Python Example

def merge_sort(arr):
    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):
    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

    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print("Before:", arr)
print("After:", merge_sort(arr))

How Merge Sort Works - C++ Example

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

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> leftPart(n1), rightPart(n2);
    for (int i = 0; i < n1; i++) leftPart[i] = arr[left + i];
    for (int j = 0; j < n2; j++) rightPart[j] = arr[mid + 1 + j];

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

    while (i < n1) arr[k++] = leftPart[i++];
    while (j < n2) arr[k++] = rightPart[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);
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(arr, 0, arr.size() - 1);
    for (int x : arr) cout << x << " ";
    return 0;
}

How Merge Sort Works - JavaScript Example

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

let arr = [38, 27, 43, 3, 9, 82, 10];
console.log("Before:", arr);
console.log("After:", mergeSort(arr));

Step-by-Step Merge Example

Suppose we want to merge [27, 38] and [3, 43].

This merge step is linear in the total size of the two sorted subarrays.

Step	Compare	Chosen Element	Result So Far
1	27 vs 3	3	[3]
2	27 vs 43	27	[3, 27]
3	38 vs 43	38	[3, 27, 38]
4	Left side empty	43	[3, 27, 38, 43]

Why Merge Sort Is Stable

Stability comes from choosing the left-hand element when merge compares equal keys. Records with equal keys therefore retain their earlier relative order.

Stable ordering is useful when records are sorted in stages, such as sorting employees by department and then by joining date without losing the earlier grouping.

Why Merge Sort Uses Extra Space

During merging, temporary arrays are usually needed to store the left and right halves. Because of this, standard Merge Sort on arrays requires O(n) extra space.

This is the main tradeoff compared with Quick Sort or Heap Sort.

Merge Sort for Linked Lists

Linked lists suit merge sort because splitting and relinking do not require random access or a full temporary array:

These properties make merge sort a natural stable choice for linked-list structures.

linked lists can be split efficiently using slow and fast pointers,
merging linked lists can be done without large extra arrays,
Quick Sort is less attractive on linked lists because random access is poor.

Bottom-Up Merge Sort

Recursion is optional. A bottom-up implementation merges runs of size 1, then 2, then 4, doubling the run width until the array is sorted while retaining O(n log n) time.

When to Use Merge Sort

Choose merge sort when one or more of these constraints matter:

guaranteed O(n log n) performance is required,
stable sorting is required,
linked lists need to be sorted,
external sorting is needed for very large data stored on disk,
parallel processing is useful.

Merge Sort vs Quick Sort vs Heap Sort

Feature	Merge Sort	Quick Sort	Heap Sort
Best / Average / Worst	O(n log n)	O(n log n) / O(n log n) / O(n^2)	O(n log n)
Extra space	O(n)	O(log n)	O(1)
Stable	Yes	No	No
Practical strength	Predictable and stable	Usually fastest for arrays	In-place with guaranteed worst case

Advantages of Merge Sort

Guaranteed O(n log n) time in all cases.
Stable sorting.
Works very well for linked lists.
Good for external sorting and large datasets.
Easy to parallelize.

Limitations of Merge Sort

Requires O(n) extra space for arrays.
Not in-place in the usual array implementation.
Often slower than Quick Sort in practice for arrays due to memory overhead.

Merge Sort Failure Cases

Thinking Merge Sort is in-place for arrays.
Forgetting that the merge step requires both halves to already be sorted.
Confusing stability with correctness.
Ignoring the extra memory cost.
Using poor midpoint calculations in some languages, causing overflow in extreme cases.

Merge Sort Rules

Merge Sort is a divide-and-conquer sorting algorithm.
Its running time is always O(n log n).
It is stable, which is a major advantage over Quick Sort and Heap Sort.
Its main tradeoff is O(n) extra memory for arrays.
It is especially useful for linked lists, external sorting, and cases needing guaranteed performance.

Before you move on