MediumArrayDivide and ConquerSortingMerge Sort

Merge Sort

1 approach, code in every language

Given an integer array nums, return an array that contains the same values arranged in non-decreasing order. You must produce the ordering yourself rather than delegating to a built-in sort routine.

A solution that compares every pair of elements is too slow for large inputs, so aim for an O(n log n) approach. Merge sort achieves this by splitting the array into halves, sorting each half, and stitching the two sorted halves back together.

Example 1

Input: nums = [5, 1, 4, 2, 8]

Output: [1, 2, 4, 5, 8]

The five values are reordered from smallest to largest.

Example 2

Input: nums = [3, -1, 3, 0]

Output: [-1, 0, 3, 3]

Duplicate values such as the two 3s remain in the result once each.

Constraints

1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4

Top-Down Merge Sort

Recursively split the array in half, sort each side, then merge the two sorted runs.

Loading animation…

Intuition

Sorting a large array is hard, but merging two already-sorted lists is easy: walk both with a pair of pointers and always take the smaller front element. Merge sort leans on this by breaking the problem down until each piece is a single element (already sorted by definition), then combining pieces upward. Every level of the recursion touches all n elements once during the merge, and there are log n levels, giving the O(n log n) bound. It is also stable, meaning equal values keep their original relative order.

Algorithm walkthrough

1If the array has one element or none, it is already sorted, so return it directly.
2Split the array at its midpoint into a left part and a right part.
3Recursively sort the left part and the right part.
4Merge the two sorted parts by repeatedly appending the smaller of the two current front elements.
5Append any leftover elements from whichever side was not exhausted and return the merged result.

Implementation

from typing import List


class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
        return self._merge(left, right)

    def _merge(self, left: List[int], right: List[int]) -> List[int]:
        merged = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged

Time

O(n log n)

Space

O(n)

The merge step allocates auxiliary storage proportional to the input size.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free