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.

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: