LESSON 286 OF 415 · DIVIDE AND CONQUER

Merge Sort in Swift: O(n log n) Time with a Temp Array

Practice O(n log n) Read the full explanation

In this video lesson we will study how the Merge Sort algorithm works, we will analyze its time and space complexities and then we will implement it:

Problem - Merge Sort:

Given an array of integers nums, sort it in ascending order using Merge Sort

Example 1:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.

STEP 1 OF 26

Guided

Ctrl + Enter to check

SWIFT · DIVIDE AND CONQUER

Merge Sort in Swift, explained

Problem overview

The method sort receives an array of integers, nums, as an inout parameter and must put it in ascending order using Merge Sort. The target is O(n log n) time and O(n) extra space.

For nums = [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5]. The result replaces the contents of the caller's array rather than being returned.

Approach: split, sort the halves, merge

Merge Sort is built on one cheap operation: merging two sorted lists into one sorted list. Walk through both lists with a pointer each, and at every step take the smaller of the two front elements. A merge of m elements takes O(m) time.

Sorting then becomes a recursion. A subarray with one element is already sorted. Otherwise split it at the middle, sort each half with the same method, and merge the two sorted halves. For [3, 1, 3, 2, 5, 4] the halves are [3, 1, 3] and [2, 5, 4]. Once each is sorted, [1, 3, 3] and [2, 4, 5], the merge produces [1, 2, 3, 3, 4, 5].

The splitting makes about log₂ n levels, and each level merges n elements in total. That gives O(n log n). Selection or insertion sort would take O(n²).

The merge needs somewhere to write its output, because writing directly into nums would overwrite values that haven't been compared yet. The lesson allocates one array, temp, as large as nums, and every merge uses the part of it matching its range.

Step by step

Declare the property temp of type [Int] above sort, initialized to []. A Swift property needs an initial value, and sort replaces it.
Size it in sort: temp = [Int](repeating: 0, count: nums.count), so it can hold any range that will be merged.
Start the recursion on the whole array: mergeSort(&nums, 0, nums.count - 1). The & passes the array as inout.
Declare mergeSort with an inout [Int] and the bounds left and right, all without labels.
Base case: when left == right the range has one element, so return.
Find middle as (left + right) / 2, a let, because it never changes.
Sort the two halves: left...middle and middle + 1...right, each with a recursive call.
Merge them with mergeSubarrays, which takes left, middle and right.
In mergeSubarrays, start three indices: i at left for the first half, j at middle + 1 for the second, and k at left for the next free slot in temp.
Merge while both halves have elements. Compare nums[i] with nums[j], copy the smaller into temp[k], advance that half's index, then advance k.
Copy leftovers. When one half runs out, the rest of the other half is already in order, so two while loops copy whatever remains of the first half and then of the second.
Copy back. A for loop over left...right writes temp[i] into nums[i].

The solution in Swift

class Solution {
    func mergeSubarrays(_ nums: inout [Int], _ left: Int, _ middle: Int, _ right: Int) {
        var i = left
        var j = middle + 1
        var k = left
        while i <= middle && j <= right {
            if nums[i] < nums[j] {
                temp[k] = nums[i]
                i += 1
            } else {
                temp[k] = nums[j]
                j += 1
            }
            k += 1
        }
        while i <= middle {
            temp[k] = nums[i]
            i += 1
            k += 1
        }
        while j <= right {
            temp[k] = nums[j]
            j += 1
            k += 1
        }
        for i in left...right {
            nums[i] = temp[i]
        }
    }
    func mergeSort(_ nums: inout [Int], _ left: Int, _ right: Int) {
        if left == right {
            return
        }
        let middle = (left + right) / 2
        mergeSort(&nums, left, middle)
        mergeSort(&nums, middle + 1, right)
        mergeSubarrays(&nums, left, middle, right)
    }
    var temp: [Int] = []
    func sort(_ nums: inout [Int]) {
        temp = [Int](repeating: 0, count: nums.count)
        mergeSort(&nums, 0, nums.count - 1)
    }
}

The Swift details worth a closer look:

inout parameters. Parameters are constants in Swift. inout lets a function modify the caller's array, and every call needs the & in front of the argument. Forgetting it is a compile error, passing value of type '[Int]' to an inout parameter requires explicit '&'.
A property shared by the methods. temp belongs to the Solution object, so mergeSubarrays can use it without it being passed around. Inside a class method, temp[k] = ... changes the property directly, with no self. needed. The same Solution object can sort several arrays, because sort resizes temp each time.
The shadowed i. The final for i in left...right declares a new constant i, which hides the earlier var i inside the loop. Nothing is wrong, but it is why that loop doesn't disturb the merge variable.
Closed ranges. left...right includes both ends. Using left..<right would leave out the last element of every merge.
A name that is already taken. sort here is the lesson's own method. On an array, Swift's built-in in-place sort is also called sort(), but the two don't conflict, because one is a method of Solution and the other of Array.
Stability. The comparison nums[i] < nums[j] takes from the right half when values are equal, so equal values can swap their relative order. For plain integers nobody can tell the difference. Using <= would keep equal elements in their original order, which matters when sorting records by a key.

Complexity

Time: O(n log n). The recursion halves the range until it reaches single elements, so it has about log₂ n levels. On each level the merges together touch every element a constant number of times: compare and copy to temp, then copy back.

Space: O(n). The array temp holds n integers. The call stack is only O(log n) deep, because the range halves with each level, so temp dominates.

Edge cases and common mistakes

Single element. The first call has left == right == 0 and returns at once. [5] stays [5].
Empty array. The first call is mergeSort(&nums, 0, -1). Since left == right is false and (0 + -1) / 2 truncates toward zero to 0, the calls keep recursing on ranges that never become single elements, and the program crashes with a stack overflow. A guard such as if nums.count < 2 { return } at the top of sort would handle it.
Duplicates. [2, 2, 2, 1, 1] becomes [1, 1, 2, 2, 2]. Equal values go through the else branch and are placed correctly.
Forgetting the leftover loops. If the right half runs out first, the rest of the left half must still be copied into temp. Without those loops the values are lost.
Merging into nums directly. Writing the merged result straight into the array overwrites elements that haven't been compared yet.
Wrong merge bounds. The left half is left...middle and the right half middle + 1...right. Using middle in both halves repeats an element.

Testing

[3, 1, 3, 2, 5, 4] gives [1, 2, 3, 3, 4, 5].
[5] gives [5].
[2, 2, 2, 1, 1] gives [1, 1, 2, 2, 2].

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free