Merge Sort

Medium20–25 min

Topics

SortingArrayDivide and ConquerRecursion

Companies

AmazonMicrosoftGoogle

Given an array of integers, sort it in non-decreasing order using **Merge Sort** — repeatedly split the array in half, sort each half, then merge the two sorted halves back together. This is the classic divide-and-conquer sort: splitting always takes O(log n) levels, and merging two sorted halves takes O(n) work at each level, giving O(n log n) overall — reliably faster than the simple O(n²) sorts on large inputs, and (unlike quicksort) with no bad-input case that degrades it.

Test Case 1:

Input:arr = [7, 2, 9, 4, 2, 8]

Output:[2, 2, 4, 7, 8, 9]

Explanation:A typical unsorted array with a repeated value.

Test Case 2:

Input:arr = []

Output:[]

Explanation:An empty array is already sorted.

Test Case 3:

Input:arr = [5]

Output:[5]

Explanation:A single element is already sorted.

Constraints

◆0 ≤ arr.length ≤ 200
◆-1000 ≤ arr[i] ≤ 1000
◆Sort in non-decreasing order

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Fresh Array at Every Merge

Good

Split the array in half, recursively sort each half, then merge the two sorted halves back together. The natural way to write this splits by slicing out brand-new left and right arrays at every single recursive call, and merge() builds yet another new array to hold the result. It's correct and easy to follow, but across all the levels of recursion, the total memory allocated for all those throwaway sub-arrays adds up to more than the O(n) a merge sort actually needs.

TimeO(n log n)

SpaceO(n log n)

Java

Try it out

class Solution {
    public int[] mergeSort(int[] arr) {
        if (arr.length <= 1) return arr;
        int mid = arr.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
        return merge(left, right);
    }

    private int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        while (i < left.length) result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];
        return result;
    }
}

Optimal — One Reused Auxiliary Buffer

Optimal

Same divide-and-conquer idea, same time complexity — but allocate exactly one auxiliary array up front, and pass it down through every recursive call by reference. Recursion now works on index ranges (lo, hi) into the original array instead of slicing out new sub-arrays, and every merge copies its range into the shared aux buffer and merges straight back into arr in place. Only one extra array ever exists, no matter how deep the recursion goes.