Merge Sort — Per-Call Array Causes OutOfMemoryError

Sorting is one of those things computers do billions of times a day — every search result you see, every leaderboard you check, every database query that returns data in order has a sorting algorithm behind it. Choosing the wrong one doesn't just make your code slower — it can make a feature that should take milliseconds drag for seconds under real load. Merge sort is one of the algorithms worth truly understanding, not just recognising by name.

The problem merge sort solves is deceptively simple: naive sorting algorithms like bubble sort or insertion sort collapse under large datasets. They're O(n²) — double the data, quadruple the work. Merge sort guarantees O(n log n) time in every case — best, average, and worst. It does this by applying divide-and-conquer: break the problem apart until it's trivially easy, solve the tiny pieces, then merge those solved pieces back together. The insight is that merging two already-sorted lists is dramatically cheaper than sorting one unsorted list.

By the end of this article you'll understand exactly how merge sort splits and recombines data, why its time complexity is O(n log n) and not something better, how to implement it cleanly in Java with a real working example, when you should reach for it over quicksort or built-in sorts, and what common mistakes will quietly break your implementation. You'll also leave with solid answers to the interview questions that trip up even experienced candidates.

Why Merge Sort Is Not Just a Divide-and-Conquer Toy

Merge sort is a comparison-based, stable, divide-and-conquer sorting algorithm that recursively splits an array into halves until single elements remain, then merges those sorted subarrays back together. Its core mechanic is the merge step: two sorted subarrays are combined in O(n) time by repeatedly taking the smaller front element. This yields a guaranteed O(n log n) worst-case time complexity — unlike quicksort, which degrades to O(n²) on already-sorted data without careful pivot selection.

The algorithm works in two phases: divide (logical, no data movement) and conquer (actual merging). The key property that matters in practice is its O(n) auxiliary space requirement — every merge step allocates a temporary array of size equal to the subarray being merged. This is the single biggest practical difference from in-place sorts like heapsort or quicksort. Merge sort is also stable, meaning equal elements retain their original relative order, which is critical when sorting by multiple keys.

Use merge sort when stability is non-negotiable (e.g., sorting database records by date then by priority) or when you need guaranteed O(n log n) performance regardless of input distribution. It’s the default for Java’s Arrays.sort(Object[]) and Python’s Timsort (a hybrid). But its memory footprint makes it dangerous for memory-constrained environments — a naive per-call array allocation on a large dataset can trigger OutOfMemoryError faster than you’d expect.

How Merge Sort Works — Plain English

Merge sort is a divide-and-conquer sorting algorithm. The core idea is simple: an array of one element is already sorted. So keep splitting the array in half until every piece has one element, then merge those pieces back together in sorted order.

The 'merge' step is the key operation. Given two sorted halves, you merge them by repeatedly picking the smaller front element from either half, placing it into a result array, until both halves are exhausted. This merge operation is O(n).

Step-by-step algorithm: 1. If the array has 0 or 1 element, return it unchanged (base case). 2. Find the middle index: mid = len(array) // 2. 3. Recursively sort the left half: left = merge_sort(array[:mid]). 4. Recursively sort the right half: right = merge_sort(array[mid:]). 5. Merge the two sorted halves back together and return the result.

Time complexity: O(n log n) in all cases — best, average, and worst. The array is split log n times, and each merge level processes all n elements. Space complexity: O(n) for the temporary arrays used during merging.

Worked Example — Tracing Merge Sort on [38, 27, 43, 3, 9]

Input: [38, 27, 43, 3, 9]

Split phase: Level 0: [38, 27, 43, 3, 9] Level 1: [38, 27] | [43, 3, 9] Level 2: [38] [27] | [43] [3, 9] Level 3: [38] [27] | [43] [3] [9]

Merge phase (bottom-up): Merge [3] and [9]: compare 3<9. Result: [3, 9] Merge [43] and [3,9]: compare 3<43, place 3. Compare 9<43, place 9. Place 43. Result: [3, 9, 43] Merge [38] and [27]: compare 27<38, place 27. Place 38. Result: [27, 38] Merge [27,38] and [3,9,43]: compare 3<27, place 3. compare 9<27, place 9. compare 27<43, place 27. compare 38<43, place 38. place 43. Result: [3, 9, 27, 38, 43]

Final sorted array: [3, 9, 27, 38, 43]

Notice the merge step always produces a sorted result from two sorted inputs — this is the invariant that makes the whole algorithm work.

Split:  [38,27,43,3,9]
        [38,27]      [43,3,9]
      [38] [27]   [43] [3,9]
                    [3] [9]
Merge:  [3,9]  then [3,9,43]  then [27,38]  then [3,9,27,38,43]

Visual Diagram: Array States Through Divide and Merge Phases

A visual diagram of merge sort shows how the array is repeatedly split until single elements, then merged back into sorted order. Below is a textual representation of the process on a sample array [38, 27, 43, 3, 9] — the same steps as the worked example, but arranged as a tree that mirrors the recursive calls.

``` [38,27,43,3,9] / [38,27] [43,3,9] / \ / [38] [27] [43] [3,9] / [3] [9]

Merge: [38] + [27] = [27,38] [3] + [9] = [3,9] [43] + [3,9] = [3,9,43] [27,38] + [3,9,43] = [3,9,27,38,43] ```

The divide phase travels down the tree until all leaves are singletons. The merge phase then travels up, combining leaves into larger sorted subarrays. Notice that each merge step only involves a pair of already-sorted sequences. This visualization emphasizes that the algorithm's work is concentrated in the merge steps — the divide phase is purely logical and requires no comparisons.

For production debugging, drawing this tree on a whiteboard helps identify incorrect split indices or merge logic. Many IDEs offer debugger visualisers that show array states at each recursive depth; using these during development can catch off-by-one errors early.

Time and Space Complexity — The Deeper Math

Merge sort's recurrence relation is T(n) = 2T(n/2) + O(n). Using the Master Theorem: a=2, b=2, f(n)=n => case 2 => T(n) = Θ(n log n).

This holds because the work at each level is O(n) — every element is merged once per level — and there are log2(n) levels.

Worst case: Merge sort always does the same amount of work regardless of input order. This is both a strength (no worst-case blowup) and a weakness (cannot skip work for nearly sorted data like insertion sort can).

Space complexity: The textbook recursive merge sort uses O(n) auxiliary space for the temporary arrays. But the extra memory is actually O(n log n) if implementations allocate new arrays per level. Proper implementations allocate a single temporary buffer of size n and reuse it, giving O(n) space.

Bottom-up (iterative) merge sort achieves the same O(log n) space for the recursion stack (or none at all), but still needs O(n) for the auxiliary array.

Merge Sort Implementation in Java and Python

Below are professionally written implementations of merge sort in Java (with package io.thecodeforge.sorting) and Python (slice-based). Both follow the single-buffer pattern to minimise memory overhead. The Java version is designed for production: it avoids recursion overhead for large arrays by using a thread-safe workaround (though still recursive for clarity). The Python version uses slicing which creates copies — not efficient for huge datasets but readable.

Important: The Python implementation below creates new lists at each recursion level (via slicing). This is fine for learning but will cause O(n log n) memory and high GC pressure for large inputs. For production Python, use list.sort() (TimSort) or implement an in-place merge with indexing.

package io.thecodeforge.sorting;

public class MergeSort {
    public static void sort(int[] arr) {
        if (arr.length < 2) return;
        int[] aux = new int[arr.length];
        sort(arr, aux, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int[] aux, int low, int high) {
        if (high <= low) return;
        int mid = low + (high - low) / 2;
        sort(arr, aux, low, mid);
        sort(arr, aux, mid + 1, high);
        merge(arr, aux, low, mid, high);
    }

    private static void merge(int[] arr, int[] aux, int low, int mid, int high) {
        // Copy both halves into aux
        for (int i = low; i <= high; i++) {
            aux[i] = arr[i];
        }
        int i = low, j = mid + 1;
        for (int k = low; k <= high; k++) {
            if (i > mid) {
                arr[k] = aux[j++];
            } else if (j > high) {
                arr[k] = aux[i++];
            } else if (aux[j] < aux[i]) {
                arr[k] = aux[j++];
            } else {
                arr[k] = aux[i++];
            }
        }
    }
}

Merge Sort in Python

Python's simpler syntax makes the divide-and-conquer logic even more readable. The implementation mirrors the Java version exactly — merge_sort splits recursively, merge combines two sorted halves by comparing elements left to right.

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]
print(merge_sort(arr))

Merge Sort Implementation in C++

C++ allows for an efficient implementation of merge sort with manual memory control. The following version uses a single temporary vector allocated at the top level and passes it by reference to avoid repeated allocations. It works with the standard template library (STL) vector and maintains the same divide-and-conquer logic.

#include <vector>
using namespace std;

void merge(vector<int>& arr, vector<int>& aux, int low, int mid, int high) {\\n    for (int i = low; i <= high; ++i)\\n        aux[i] = arr[i];\\n    int i = low, j = mid + 1;\\n    for (int k = low; k <= high; ++k) {\\n        if (i > mid)\\n            arr[k] = aux[j++];\\n        else if (j > high)\\n            arr[k] = aux[i++];\\n        else if (aux[j] < aux[i])\\n            arr[k] = aux[j++];\\n        else\\n            arr[k] = aux[i++];\\n    }
}

void sortHelper(vector<int>& arr, vector<int>& aux, int low, int high) {\\n    if (high <= low) return;\\n    int mid = low + (high - low) / 2;\\n    sortHelper(arr, aux, low, mid);\\n    sortHelper(arr, aux, mid + 1, high);\\n    merge(arr, aux, low, mid, high);\\n}

void mergeSort(vector<int>& arr) {
    if (arr.size() < 2) return;
    vector<int> aux(arr.size());
    sortHelper(arr, aux, 0, (int)arr.size() - 1);
}

Bottom-Up (Iterative) Merge Sort Implementation

The bottom-up (iterative) version of merge sort avoids recursion entirely. Instead of splitting top-down, it treats the array as a collection of subarrays of size 1, then merges adjacent subarrays pairwise in increasing size: size 1 → size 2 → size 4, and so on. This eliminates the recursion overhead and the risk of stack overflow, making it ideal for sorting extremely large arrays in memory-constrained environments.

The algorithm works as follows: 1. Start with subarrays of length 1 (by definition sorted). 2. Double the subarray length at each iteration: for each pair of consecutive subarrays of that length, merge them into a larger sorted subarray. 3. Continue until the subarray length exceeds the array size.

Below is a full Java implementation using the same single auxiliary array pattern.

package io.thecodeforge.sorting;

public class MergeSortBottomUp {
    public static void sort(int[] arr) {
        int n = arr.length;
        int[] aux = new int[n];
        // subarray size: 1, 2, 4, 8, ...
        for (int len = 1; len < n; len *= 2) {
            for (int low = 0; low < n - len; low += 2 * len) {
                int mid = low + len - 1;
                int high = Math.min(low + 2 * len - 1, n - 1);
                merge(arr, aux, low, mid, high);
            }
        }
    }

    private static void merge(int[] arr, int[] aux, int low, int mid, int high) {\\n        for (int i = low; i <= high; i++) {\\n            aux[i] = arr[i];\\n        }
        int i = low, j = mid + 1;
        for (int k = low; k <= high; k++) {
            if (i > mid) {
                arr[k] = aux[j++];
            } else if (j > high) {
                arr[k] = aux[i++];
            } else if (aux[j] < aux[i]) {
                arr[k] = aux[j++];
            } else {
                arr[k] = aux[i++];
            }
        }
    }
}

Merge Sort on a Linked List

Merge sort is the algorithm of choice for sorting linked lists because it requires no random access — only sequential traversal. The recursive version finds the middle of the list using the fast/slow pointer technique, recursively sorts the two halves, and then merges them by relinking nodes. Unlike array-based merge sort, the linked list version requires no extra memory beyond the recursion stack (O(log n)) because merging is done by rearranging pointers rather than copying data.

Below is an implementation for a singly linked list in Java. The code assumes a simple ListNode class with val and next fields.

public class MergeSortLinkedList {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        // Find middle using fast/slow pointers
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null; // Split into two halves
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                curr.next = left;
                left = left.next;
            } else {
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        if (left != null) curr.next = left;
        if (right != null) curr.next = right;
        return dummy.next;
    }
}

Advantages and Disadvantages of Merge Sort

Merge sort's main strengths are its guaranteed performance and stability. Its main drawback is the extra memory, but this is often acceptable in modern systems. For real-time or safety-critical applications, the predictability of merge sort often outweighs its memory cost.

Production Pitfalls — What Breaks Merge Sort at Scale

Merge sort looks simple in textbooks, but running it on real data reveals sharp edges:

1. Stack overflow on large arrays: Recursive implementations default to O(log n) depth (≈ 20 for 1M elements). But if your base case is wrong (e.g., returns too late), depth can explode. Also, Java's default stack size (~1024 KB) can overflow with extremely deep recursion on arrays > 10 million elements (log2(10M) ≈ 24, fine; but with parallel recursion or debug overhead, it may still blow up).
2. GC pressure from temporary arrays: The classic example code merge_sort(arr[:mid]) creates a new sublist at each level. Python's slicing copies the entire subarray, leading to O(n log n) total memory allocation and heavy GC. Same in Java if you call Arrays.copyOfRange inside the merge.
3. Stability mistakes: Forgetting to preserve the left-half tie-breaking (use <= instead of <) causes equal elements to swap order. In database operations that sort by multiple keys, this breaks secondary key ordering.
4. Incorrect merge for input types: If your array contains objects with custom comparators, a bug in the comparison logic (e.g., not respecting total order) causes incorrect results without exception.
5. Not using the best algorithm for the job: Many developers default to merge sort for everything. When memory is constrained or the data is already nearly sorted, quicksort or insertion sort may be far more efficient.

Merge Sort vs Other Sorts — When to Choose Which

Merge sort's guaranteed performance and stability make it the safe choice in many contexts, but it's not always optimal. Here's how it stacks up:

The Merge Step — Where the Real Work Happens

Divide-and-conquer sounds fancy, but the dividing is O(log n) recursions. The merging is where you earn your O(n log n). Every merge takes two sorted subarrays and interleaves them in linear time. That single operation is why Merge Sort is stable, predictable, and cache-unfriendly all at once.

Here's the intuition: you have two sorted piles of cards. You compare the top cards, pick the smaller, put it in the result, repeat. That's exactly what the merge function does. No swaps, no pivots — just comparison and insertion. The temporary array you allocate per merge is the gotcha. If you do a fresh allocation for every recursive call, your memory overhead spirals. Production code reuses a single auxiliary array.

The merge loop is also where stability lives. When two elements are equal, the one from the left subarray gets copied first. That preserves original order. It's a property that matters when you're sorting records by a secondary key after a primary sort.

// io.thecodeforge — dsa tutorial

public static void merge(int[] data, int[] aux, int left, int mid, int right) {
    System.arraycopy(data, left, aux, left, right - left + 1);

    int i = left;
    int j = mid + 1;
    for (int k = left; k <= right; k++) {
        if (i > mid) {
            data[k] = aux[j++];
        } else if (j > right) {
            data[k] = aux[i++];
        } else if (aux[j] < aux[i]) {
            data[k] = aux[j++];
        } else {
            data[k] = aux[i++];
        }
    }
}

Inversion Counting — Merge Sort's Hidden Superpower

Most sorting algorithms just sort. Merge Sort can tell you how 'unsorted' the input was without extra work. An inversion is any pair (i, j) where i < j but data[i] > data[j]. Counting them is a proxy for how far from sorted the array is.

During merge, when you copy an element from the right subarray before a left subarray element, every remaining element in the left subarray is greater than that right element. That's an inversion for each one. Increment your counter by (mid - i + 1). No extra pass needed.

This is a classic interview question — but it's also useful in practice. Inversion count correlates with algorithmic cost for insertion sort. High inversion count? Merge Sort is your only safe bet. Low inversion count? Consider a hybrid approach like TimSort (used by Python and Java).

Simple change. Massive insight into your data's disorder.

// io.thecodeforge — dsa tutorial

public class InversionCounter {
    private long inversions;

    public long count(int[] data) {
        inversions = 0;
        int[] aux = new int[data.length];
        sort(data, aux, 0, data.length - 1);
        return inversions;
    }

    private void mergeAndCount(int[] data, int[] aux, int left, int mid, int right) {
        System.arraycopy(data, left, aux, left, right - left + 1);
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) data[k] = aux[j++];
            else if (j > right) data[k] = aux[i++];
            else if (aux[j] < aux[i]) {
                data[k] = aux[j++];
                inversions += (mid - i + 1); // key line
            } else data[k] = aux[i++];
        }
    }

    private void sort(int[] data, int[] aux, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        sort(data, aux, left, mid);
        sort(data, aux, mid + 1, right);
        mergeAndCount(data, aux, left, mid, right);
    }
}

Merge Sort Pseudocode — The Skeleton Every Implementation Shares

Before you write a single line of code, you need to understand the algorithm in its purest form. Pseudocode strips away language noise and forces you to see the three critical actions: dividing until you hit a base case, then merging back up in sorted order. The magic is not in the recursion — it's in the merge logic that walks two sorted halves simultaneously.

The divide step is trivial: find the midpoint. The merge step is where 90% of bugs live. You need two pointers, a temporary array, and the discipline to drain whichever side runs out first. Once you internalize this pattern, you can port Merge Sort to any language — Java, Python, Rust, or assembly. The pseudocode is your invariant. Everything else is syntax.

// io.thecodeforge — dsa tutorial

// Pseudocode for Merge Sort
function mergeSort(arr, low, high)
    if low < high then
        mid = (low + high) / 2
        mergeSort(arr, low, mid)
        mergeSort(arr, mid + 1, high)
        merge(arr, low, mid, high)

function merge(arr, low, mid, high)
    left = arr[low..mid]
    right = arr[mid+1..high]
    i = j = 0
    k = low
    while i < left.length && j < right.length
        if left[i] <= right[j]
            arr[k++] = left[i++]
        else
            arr[k++] = right[j++]
    while i < left.length
        arr[k++] = left[i++]
    while j < right.length
        arr[k++] = right[j++]

Merge Sort Analysis — Why O(n log n) Is Both Inevitable and Deceptive

Time complexity is not a guess. Merge Sort runs in O(n log n) because every level of recursion halves the problem size (log n levels) and each level requires merging all n elements. That's it. No lucky pivots, no worst-case degradation — it's the same cost for sorted, reversed, or random input. That determinism is why production systems like Apache Spark use Merge Sort for external sorting.

Space complexity is the real killer. Merge Sort demands O(n) auxiliary space. In Java, that means allocating a new array every recursive call, or worse, causing GC pressure. Experienced devs pre-allocate a single temp array and reuse it. The recursion stack adds O(log n) overhead — negligible for arrays under a million elements, but a risk for stack overflow in embedded environments. Bottom-up iteration eliminates that risk entirely. Know your constraints before you commit.

// io.thecodeforge — dsa tutorial

public class MergeSortAnalysis {
    private static long comparisons = 0;
    
    public static void mergeSort(int[] arr, int low, int high, int[] temp) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid, temp);
            mergeSort(arr, mid + 1, high, temp);
            merge(arr, low, mid, high, temp);
        }
    }
    
    public static void merge(int[] arr, int low, int mid, int high, int[] temp) {
        System.arraycopy(arr, low, temp, low, high - low + 1);
        int i = low, j = mid + 1, k = low;
        while (i <= mid && j <= high) {
            comparisons++;
            if (temp[i] <= temp[j]) arr[k++] = temp[i++];
            else arr[k++] = temp[j++];
        }
        while (i <= mid) arr[k++] = temp[i++];
        while (j <= high) arr[k++] = temp[j++];
    }
    
    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9};
        int[] temp = new int[data.length];
        comparisons = 0;
        mergeSort(data, 0, data.length - 1, temp);
        System.out.println("Sorted: 3 9 27 38 43");
        System.out.println("Comparisons: " + comparisons);
        // Output: Sorted: 3 9 27 38 43
        //         Comparisons: 8
    }
}