Sort an Array: Merge Sort from Scratch

Sort an Array is LeetCode problem 912. Given an array of integers nums, sort the array in ascending order and return it. You must solve it without using any built-in sort functions, and the expected time complexity is O(n log n).

The problem

You are given an integer array and need to return it sorted in ascending order. The catch is that naive O(n^2) sorting algorithms like bubble sort and insertion sort will time out on large inputs. You need an efficient algorithm.

Example: nums = [5, 2, 3, 1] returns [1, 2, 3, 5]. Another example: nums = [5, 1, 1, 2, 0, 0] returns [0, 0, 1, 1, 2, 5].

The brute force approach

The simplest sorting algorithms run in O(n^2) time. Bubble sort repeatedly swaps adjacent elements that are out of order. Selection sort finds the minimum element and places it at the front, then repeats for the remaining array. Insertion sort builds a sorted portion one element at a time, inserting each new element into its correct position.

All of these work correctly, but they are too slow. When nums can contain up to 50,000 elements, an O(n^2) algorithm performs up to 2.5 billion operations. That is far too many. You need an algorithm that runs in O(n log n) time, and merge sort is the classic choice.

The key insight

Merge sort uses a divide-and-conquer strategy. Instead of sorting the whole array at once, you split it in half, sort each half recursively, and then merge the two sorted halves back together. The merge step is the key: given two sorted arrays, you can combine them into one sorted array in O(n) time by walking two pointers through them and always picking the smaller element.

Step-by-step walkthrough

The code

def sortArray(nums):
    if len(nums) <= 1:
        return nums

    mid = len(nums) // 2
    left = sortArray(nums[:mid])
    right = sortArray(nums[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

The sortArray function handles the divide step. If the array has zero or one element, it is already sorted, so return it. Otherwise, split at the midpoint, recursively sort each half, and merge the results.

The merge function handles the conquer step. It walks two pointers i and j through the left and right halves. At each step, it picks the smaller of left[i] and right[j] and appends it to the result. When one half is exhausted, it appends whatever remains from the other.

The <= comparison in the merge function preserves the relative order of equal elements. This makes the sort stable, which can matter in follow-up problems or real-world applications.

Complexity analysis

The time complexity is O(n log n) because there are log n levels of recursion, and at each level the merge step processes all n elements exactly once.

The space complexity is O(n) because each merge call creates a new result array. In total, the merged arrays at any single level of recursion use O(n) space. The recursion stack adds O(log n), but that is dominated by the O(n) merge buffers.

The building blocks

Divide and conquer

The divide-and-conquer pattern appears throughout algorithm design. You break a problem into smaller subproblems, solve each one independently, and combine the results. Merge sort is the textbook example: divide the array in half, sort each half, merge. The same strategy powers problems like Kth Largest Element (quickselect uses partition as its divide step) and binary search, where you discard half the search space at each step.

Merging two sorted sequences

The merge function is a reusable building block on its own. Given two sorted inputs, produce a single sorted output by comparing front elements and always taking the smaller one. You will see this same logic in Merge Sorted Array (merging in place from the back), Merge Two Sorted Lists (merging linked lists), and Merge K Sorted Lists (extending the idea to k inputs with a heap).

Edge cases

• Empty array. Return []. The base case handles this since len(nums) <= 1.
• Single element. Return the array as is. Already sorted by definition.
• Already sorted input. Merge sort still divides and merges, but each merge step just walks through both halves in order. The time complexity does not improve for sorted input.
• All duplicate values. The <= comparison ensures stability and correctness. Every comparison picks the left element first, preserving order.

From understanding to recall

Merge sort is one of the most fundamental algorithms in computer science, and most people understand how it works after reading it once. The challenge is reproducing it under pressure. Where exactly do you split? Do you use nums[:mid] or nums[:mid+1]? In the merge function, what happens when one side runs out of elements first?

These details are small but easy to get wrong when you are coding on a whiteboard or in a timed interview. Reading the solution gives you understanding. Writing it from scratch, repeatedly, with increasing gaps between sessions, gives you recall. Spaced repetition handles the scheduling so you review just often enough to keep the pattern locked in.

The merge function in particular is worth drilling on its own. It shows up as a subroutine in so many problems that making it second nature pays dividends across your entire problem set.

Related posts

• Sort List - Merge sort applied to a linked list, using slow/fast pointers to find the midpoint
• Merge Sorted Array - The merge step done in place by filling from the end
• Kth Largest Element - Another divide-and-conquer sorting idea using quickselect's partition