ReviseAlgo Logo

Sorting Algorithms

Merge Sort

Divide, conquer, and merge — the O(N log N) stable sorting algorithm used in practice.

Last Updated: August 2, 2026 • 20 min read

1. Introduction

What is Merge Sort?

Merge Sort is an efficient, general-purpose, comparison-based sorting algorithm. It utilizes a Divide and Conquer paradigm to split problems into smaller subproblems, solve them recursively, and combine their results.

Why is it Important?

Unlike Quick Sort, Merge Sort guarantees O(N log N) time complexity in all cases (best, average, worst). It is stable (preserves relative order of duplicate elements) and works extremely well on data structures without random access, such as Linked Lists.

Where is it Used?

  • External Sorting: Sorting datasets that are too large to fit into primary memory (RAM) by loading chunks, sorting them, and merging them on disk.
  • Timsort: The default sorting algorithm for Python, Java (objects), and Android, which uses Merge Sort as its high-level framework.

    • 2. Mental Model: Merging Two Stacks

    Imagine you have two stacks of cards, both already sorted from lowest to highest.

  • Stack A: [2, 5, 8]
  • Stack B: [3, 6, 9]

    • You want to merge them into a single sorted stack. You compare the top card of both stacks: 1. Compare 2 and 3: 2 is smaller. Put 2 into the output. 2. Compare 5 and 3: 3 is smaller. Put 3 into the output. 3. Compare 5 and 6: 5 is smaller. Put 5 into the output. 4. Continue this two-pointer comparison until one stack is empty, then append all remaining cards of the other stack.

    3. Core Algorithm & Implementations

    Merge Sort recursively divides the array at its midpoint until each subarray contains exactly 1 element (which is naturally sorted). It then calls the merge utility to weave the subarrays back together in sorted order.

    4. Visual Trace: Split & Merge recursion

    Below is the recursive splitting and merging trace for the array [38, 27, 43, 3]:

    5. Real-World Applications

  • Sorting Linked Lists: Unlike arrays, linked lists can merge two sorted sublists in O(1) auxiliary space by simply updating pointer links, making Merge Sort the absolute best sorting algorithm for linked list structures.
  • External Merge Sort: Databases sorting tables larger than RAM split files into page-sized blocks, sort each block using internal sort, then stream-merge blocks sequentially using min-priority queues.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test recursion mechanics and list manipulations using Merge Sort:
  • "Sort a singly linked list in O(N log N) time and O(1) auxiliary space." -> Use recursive split via fast/slow pointers, then merge in-place.
  • "Count the number of inversions in an array (pairs (i, j) where i < j and arr[i] > arr[j])." -> Modify the merge step of Merge Sort! When copying an element from the right subarray, add (mid + 1 - i) to the inversion count.

    • Common Mistakes

    Warning: 1. Memory Leak or Stack Overflow in C++: Allocating vector allocations dynamically inside standard recursive calls can cause memory fragmentation or leaks if not managed. Always declare local stack-allocated arrays/vectors or pre-allocate a single shared temp buffer.
    > 2. Off-by-one Mid Calculations: Calculating mid as (left + right) / 2 can cause integer overflow for extremely large arrays. Use left + (right - left) / 2 instead.

    7. Summary

  • Dividing: Splitting index range in half takes O(1) time.
  • Merging: Blending two sorted blocks of sizes L and R takes O(L + R) time and O(L + R) helper space.
  • Stability: Ensured by checking arr[i] <= arr[j] (the equality sign guarantees that the element in the left half stays before the right).
  • Linked Lists: Merge Sort sorts lists with O(1) auxiliary space.

    • 8. Quiz

    Question 1: Why does Merge Sort have a spatial complexity of O(N)? Answer: During the merge phase, we need a temporary array of size N to store the sorted elements before copying them back to the original array. We cannot merge two sorted subarrays in-place inside a single array in linear time without shifting elements, which would degrade the time complexity to O(N²).
    Question 2: What determines the stability of the Merge Sort implementation? Answer: The comparison operator in the merge step: if (arr[i] <= arr[j]). The <= guarantees that if elements are equal, the one in the left subarray (which originally appeared earlier in the array) is chosen first, preserving stability. If we change it to < it becomes unstable.
    Question 3: How does the "Count Inversions" problem use Merge Sort? Answer: An inversion occurs when arr[i] > arr[j] for i < j. During the merge step, if arr[j] (from the right half) is smaller than arr[i] (from the left half), then it is smaller than all remaining elements in the left half (from index i to mid). Thus, we can count all these inversions instantly in O(1) by adding (mid - i + 1) to our counter.
    Question 4: What is the recurrence relation for Merge Sort and how does the Master Theorem solve it? Answer: The recurrence is T(N) = 2T(N/2) + O(N). According to the Master Theorem: a=2, b=2, d=1. Since log_b(a) = log_2(2) = 1 = d, the solution is T(N) = O(N^d log N) = O(N log N).
    Question 5: Does Merge Sort benefit from the input array already being sorted? Answer: No, standard Merge Sort is non-adaptive. It performs the exact same splits and merges, taking O(N log N) comparisons and O(N log N) copies regardless of whether the input is sorted, reversed, or random.