Merge Sort Algorithm O n log n Stable Sort: Tutorial, Examples, FAQs & Interview Tips

What is Merge Sort?

Merge Sort is a classic divide-and-conquer sorting algorithm. It repeatedly divides the array into smaller halves until each part becomes very small, then merges those parts back together in sorted order.

Merge Sort is important because it guarantees O(n log n) time in the best, average, and worst cases. It is also stable, which means equal elements keep their original relative order.

Core Idea

Merge Sort works in two major phases:

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

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

Key Insight: Merge Sort trades extra space for predictable speed. It uses additional memory during merging, but in return it gives guaranteed O(n log n) performance and stability.

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].

Divide Phase

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 Phase

Merge single elements into sorted pairs
Merge sorted pairs into larger sorted subarrays
Continue until one fully sorted array remains

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

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

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

#include 
#include 
using namespace std;

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

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

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].

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]

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

Why Merge Sort Is Stable

Merge Sort is stable because when two equal elements are compared during merging, the element from the left subarray is taken first. This preserves the original relative order of equal elements.

Stability matters in applications where records are sorted by multiple keys.

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

Merge Sort is especially good for linked lists because:

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.

This is why Merge Sort is often the preferred sorting algorithm for linked-list structures.

Bottom-Up Merge Sort

Merge Sort does not always need recursion. A bottom-up version starts by merging subarrays of size 1, then size 2, then size 4, and so on. This avoids recursion while keeping the same O(n log n) time complexity.

When to Use Merge Sort

Merge Sort is a good choice when:

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.

Common Mistakes

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.

Key Takeaways

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.

Previous Next