Log inSign up
mediumGeeksforGeeksNot Started

Merge Sort

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of integers nums, sort the array in ascending order using the Merge Sort algorithm.

You must implement a stable divide-and-conquer sorting algorithm with a time complexity of `O(N log N)` in all cases (best, average, worst).

Example 1:

Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: The array is split into [5, 2] and [3, 1], recursively sorted to [2, 5] and [1, 3], and merged to [1, 2, 3, 5].

Example 2:

Input: nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]
Explanation: Duplicates are handled stably, resulting in a sorted sequence.

Example 3:

Input: nums = [10]
Output: [10]
Explanation: A single element array is trivially sorted.

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Recursion and call stack mechanics
  • Two-pointer merge technique for two sorted arrays
  • Divide and conquer paradigm

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Divide, Conquer, and Combine methodology.
  • Understand why tie-breaking with <= maintains stability.
  • Optimize memory footprint by passing a single reusable auxiliary buffer.
  • Analyze recurrence relations using Master Theorem: T(N) = 2T(N/2) + O(N) -> O(N log N).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Requirement for stable sorting with guaranteed O(N log N) worst-case time.
  • Counting inversions or smaller elements after self in an array.
  • Sorting linked lists or external datasets (external sorting) where random access is slow.

Algorithmic Decision Tree:

  • If sorting linked lists with O(1) space -> Merge Sort (splicing nodes without extra array buffer).
  • If counting cross-inversions -> Merge Sort merge step.
  • If guaranteed O(N log N) with stability is needed for arrays -> Merge Sort with O(N) buffer.

Connected Patterns:

Count Inversions in an ArraySort List (Linked List Merge Sort)Count of Smaller Numbers After Self

1. Out-of-Place List Merging (Brute Force)

Intuition

Divide the array into two halves until length <= 1. Recursively sort each half, then merge the two sorted halves into a newly allocated output array.

When to apply: Use to understand divide-and-conquer before optimizing memory allocations.

Recursive Divide & Conquer Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [38, 27, 43, 3, 9, 82, 10]
Current operationSTEP 1 OF 6
Array: [38, 27, 43, 3, 9, 82, 10]
Visual state
Values and pointers at this exact step
pointers
S
38
27
43
3
9
82
10
0
↑ Left half
1
2
3
4
5
6
Variables at this step
left
[38,27,43]
right
[3,9,82,10]
Check / comparison
Divide step.
Decision / next transition
Split into two subproblems.
Why this step matters

Array: [38, 27, 43, 3, 9, 82, 10]. Split at mid=3 into left [38, 27, 43] and right [3, 9, 82, 10].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] sortArray(int[] nums) {
6 if (nums.length <= 1) return nums;
7 int mid = nums.length / 2;
8 int[] left = sortArray(Arrays.copyOfRange(nums, 0, mid));
9 int[] right = sortArray(Arrays.copyOfRange(nums, mid, nums.length));
10
11 int[] res = new int[nums.length];
12 int i = 0, j = 0, k = 0;
13 while (i < left.length && j < right.length) {
14 if (left[i] <= right[j]) res[k++] = left[i++];
15 else res[k++] = right[j++];
16 }
17 while (i < left.length) res[k++] = left[i++];
18 while (j < right.length) res[k++] = right[j++];
19 return res;
20 }
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 int[] nums = {38, 27, 43, 3, 9, 82, 10};
26 System.out.println("Sorted: " + Arrays.toString(sol.sortArray(nums)));
27 }
28}

Time & Space Complexity

  • Time complexity: O(n log n) — n elements at each of log n levels of recursion.
  • Space complexity: O(n log n) — Repeated subarray allocations across the call tree.

Why Brute Force Doesn't Scale:

Allocating small temporary vectors at every recursion node triggers millions of malloc/free cycles. A single pre-allocated auxiliary buffer reduces memory allocations from O(N) down to 1.

For N = 10,000,000 integers, naive slicing allocates ~100MB across ~20M tiny objects, triggering massive GC pauses. Pre-allocated buffer allocates exactly one 40MB array upfront.

2. Bottom-Up Iterative Merge Sort

Intuition

Double window width from 1 to n. For each pair of adjacent windows of width w, merge them in-place using a temporary buffer. This guarantees O(n log n) time iteratively.

When to apply: Use to eliminate recursion call stack frames.

Bottom-Up Iterative Doubling Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [38, 27, 43, 3, 9, 82, 10]
Current operationSTEP 1 OF 6
Pass 1 (width=1): Merge pairs of size 1: (38, 27)->[27, 38], (43, 3)->[3, 43], (9, 82)->[9, 82], [10]->[10]
Visual state
Values and pointers at this exact step
pointers
S
27
38
3
43
9
82
10
0
↑ w=1
1
2
3
4
5
6
Variables at this step
width1
[27,38,3,43,9,82,10]
Check / comparison
Width 1 merge.
Decision / next transition
Array becomes [27, 38, 3, 43, 9, 82, 10].
Why this step matters

Pass 1 (width=1): Merge pairs of size 1: (38, 27)->[27, 38], (43, 3)->[3, 43], (9, 82)->[9, 82], [10]->[10].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] sortArray(int[] nums) {
6 int n = nums.length;
7 int[] temp = new int[n];
8 for (int w = 1; w < n; w *= 2) {
9 for (int i = 0; i < n; i += 2 * w) {
10 int mid = Math.min(i + w, n);
11 int right = Math.min(i + 2 * w, n);
12 merge(nums, temp, i, mid, right);
13 }
14 }
15 return nums;
16 }
17
18 private void merge(int[] nums, int[] temp, int l, int m, int r) {
19 int i = l, j = m, k = l;
20 while (i < m && j < r) {
21 if (nums[i] <= nums[j]) temp[k++] = nums[i++];
22 else temp[k++] = nums[j++];
23 }
24 while (i < m) temp[k++] = nums[i++];
25 while (j < r) temp[k++] = nums[j++];
26 for (i = l; i < r; i++) nums[i] = temp[i];
27 }
28 }
29
30 public static void main(String[] args) {
31 Solution sol = new Solution();
32 int[] nums = {38, 27, 43, 3, 9, 82, 10};
33 System.out.println("Sorted: " + Arrays.toString(sol.sortArray(nums)));
34 }
35}

Time & Space Complexity

  • Time complexity: O(n log n) — log n passes over array of size n.
  • Space complexity: O(n) — Single auxiliary buffer array of size n.

3. Pre-Allocated Buffer Merge Sort (Optimal & Standard)

Intuition

1. Allocate a single temporary array temp of size n before recursion. 2. Recursively divide: sort(nums, temp, low, mid) and sort(nums, temp, mid + 1, high). 3. Merge: copy segment nums[low..high] into temp, then scan with two pointers into nums[low..high]. Reusing the buffer eliminates garbage collection overhead and repeated allocations.

When to apply: Use as the canonical optimal industry standard for stable merge sort.

Pre-Allocated Buffer Merge Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [38, 27, 43, 3, 9, 82, 10]
Current operationSTEP 1 OF 6
Array: [38, 27, 43, 3, 9, 82, 10]
Visual state
Values and pointers at this exact step
pointers
S
38
27
43
3
9
82
10
0
↑ low=0
1
2
3
↑ mid=3
4
5
6
Variables at this step
low
0
high
6
mid
3
Check / comparison
Divide at mid=3.
Decision / next transition
Recurse on [0..3] and [4..6].
Why this step matters

Array: [38, 27, 43, 3, 9, 82, 10]. Pre-allocate temp array of size 7. mid = 3.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] sortArray(int[] nums) {
6 int[] temp = new int[nums.length];
7 mergeSort(nums, temp, 0, nums.length - 1);
8 return nums;
9 }
10
11 private void mergeSort(int[] nums, int[] temp, int low, int high) {
12 if (low >= high) return;
13 int mid = low + (high - low) / 2;
14 mergeSort(nums, temp, low, mid);
15 mergeSort(nums, temp, mid + 1, high);
16 merge(nums, temp, low, mid, high);
17 }
18
19 private void merge(int[] nums, int[] temp, int low, int mid, int high) {
20 for (int i = low; i <= high; i++) temp[i] = nums[i];
21 int i = low, j = mid + 1, k = low;
22 while (i <= mid && j <= high) {
23 if (temp[i] <= temp[j]) nums[k++] = temp[i++];
24 else nums[k++] = temp[j++];
25 }
26 while (i <= mid) nums[k++] = temp[i++];
27 }
28 }
29
30 public static void main(String[] args) {
31 Solution sol = new Solution();
32 int[] nums = {38, 27, 43, 3, 9, 82, 10};
33 System.out.println("Sorted: " + Arrays.toString(sol.sortArray(nums)));
34 }
35}

Time & Space Complexity

  • Time complexity: O(n log n) — Guaranteed O(n log n) comparisons in all cases (worst, average, best).
  • Space complexity: O(n) — Single O(n) buffer array + O(log n) recursion call stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Subarray Slicing / Naive Allocations)O(N log N)O(N log N)At every recursive call, slice the array into new left and right subarrays and return a newly merged array.Repeated memory allocations at every level of the recursion tree.
2.Better (Bottom-Up Iterative Merge Sort)O(N log N)O(N)Merge subarrays of size 1, 2, 4, 8... iteratively without using recursion stack frames.Requires auxiliary buffer for merging.
3.Optimal (Top-Down Divide & Conquer with Reusable Buffer)OptimalO(N log N)O(N)Divide recursively and merge in-place using a single pre-allocated temporary buffer of size N.Auxiliary memory write and copy back phase.

Common Pitfalls & Crucial Edge Cases

Allocating new arrays inside every recursive helper

Causes massive memory allocation overhead and degrades cache performance to O(N log N) space.

Using strict `<` instead of `<=` in merge comparison

Breaks sort stability by taking elements from the right subarray ahead of identical elements in the left subarray.

Forgetting to copy merged elements back to original array

If temp is modified without copying back into nums[low...high], subsequent merges at parent levels read unsorted data.

Crucial Edge Cases to Validate:

  • Already Sorted Array ([1, 2, 3, 4]): Still performs full divide and merge steps in O(N log N).
  • Single Element Array ([42]): Base case low >= high hits immediately, 0 swaps or merges.
  • Duplicate Elements ([2, 2, 2, 2]): nums[i] <= nums[j] condition ensures left elements are picked first, preserving stability.
  • Odd-length Arrays ([7, 3, 9, 2, 8]): Subarrays split into sizes 3 and 2 cleanly without index calculation errors.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What property makes Merge Sort preferred over QuickSort when sorting objects with secondary keys?

2.What is the recurrence relation for standard Top-Down Merge Sort?

3.Why is standard Merge Sort rarely used as an in-place sort for arrays?

Back to DSA Sheet