Merge Sort In Swift

This post was originally published on 02/09/17 and updated on 02/05/23.

Let's start by looking at the mechanics of merge sort:

Understanding the Mechanics of Merge Sort

The divide-and-conquer approach is a technique used by merge sort to sort an array of elements. It starts by dividing the input array into two halves and continues to divide each half until each subarray contains only one element. This approach allows the algorithm to break down a complex problem into smaller, more manageable subproblems that can be solved more easily.

Once the input array has been divided into subarrays containing only one element, the algorithm begins the merging process. The merging process involves comparing and merging adjacent subarrays into larger sorted subarrays. This process is repeated until the entire input array is sorted and merged into a single sorted array. The merging process ensures that the elements in the final sorted array are in the correct order.

Time and space complexity

Merge sort has a time complexity of O(n log n), where n is the number of elements in the array. This is because the algorithm divides the array into two halves in each recursive step, and each step requires O(n) time to merge the two sorted halves. The log n term comes from the number of recursive steps required to divide the array into single elements.

The space complexity of merge sort is O(n), as the algorithm requires an auxiliary array to store the sorted elements while merging the two halves. This is because the algorithm sorts the elements in-place, meaning that it operates on the original array rather than creating a new one.

It's important to note that the time and space complexities of merge sort are the same regardless of the order of the elements in the original array. This makes it a stable sorting algorithm, meaning that elements that have the same value maintain their relative order in the final sorted array.

Example

We want to sort the array [98,1,45,13,6]. First, the array will be divided into subarrays [98,1,45] and [13,6]. Then, the divided lists will be divided again. This process will be continued until  every array has exactly one item. In the picture, this is accomplished in line four.

Then the merging process starts: Always two lists will be merged. So the two arrays [98] and [1] will be merged into [1,98]. Additionally, the arrays [45] and [13] will be merged into [13,45]. It's important to note that in this merging process, the elements get sorted: We look at the first elements and take the smaller element. Then we continue until both arrays are merged.

The process will be repeated until only one list is left – the sorted list.

Merge Sort in Swift

Now let’s implement the algorithm in Swift. There are different approaches for solving that problem, we will take a recursive one:

import Foundation

func merge(left:[Int],right:[Int]) -> [Int] {
    var mergedList = [Int]()
    var left = left
    var right = right
    
    while left.count > 0 && right.count > 0 {
        if left.first! < right.first! {
            mergedList.append(left.removeFirst())
        } else {
            mergedList.append(right.removeFirst())
        }
    }

    return mergedList + left + right
}

func mergeSort(list:[Int]) -> [Int] {
    guard list.count > 1 else {
        return list
    }
    
    let leftList = Array(list[0..<list.count/2])
    let rightList = Array(list[list.count/2..<list.count])
    
    return merge(left: mergeSort(list:leftList), right: mergeSort(list:rightList))
}

The function mergeSort divides the list into two lists and returns the merged and sorted list by using the function merge. Within the function call, the function calls itself recursively for both lists. When mergeSort gets a list, that has just one element, it returns the whole list.

The function merge always compares the first items of the two lists and appends the smaller item to the new sorted list.

Testing the algorithm

Now we can test the algorithm:

var list = [Int]()

for _ in 0..<100 {
    list.append(Int(arc4random_uniform(UInt32(1000))))
}

print(list)

print()

print(mergeSort(list: list))

The generated output is:

[723, 647, 801, 378, 630, 789, 654, 1, 66, 848, 178, 837, 79, 921, 880, 663, 835, 497, 459, 59, 940, 380, 37, 897, 29, 346, 11, 192, 955, 652, 276, 205, 903, 935, 762, 681, 211, 218, 586, 393, 372, 708, 202, 660, 35, 654, 392, 839, 710, 948, 50, 726, 999, 79, 881, 324, 22, 49, 564, 639, 117, 256, 978, 179, 942, 710, 7, 389, 701, 128, 239, 548, 848, 771, 538, 548, 359, 50, 752, 892, 87, 107, 959, 717, 846, 546, 417, 350, 212, 239, 938, 788, 75, 16, 664, 897, 588, 368, 199, 350]

[1, 7, 11, 16, 22, 29, 35, 37, 49, 50, 50, 59, 66, 75, 79, 79, 87, 107, 117, 128, 178, 179, 192, 199, 202, 205, 211, 212, 218, 239, 239, 256, 276, 324, 346, 350, 350, 359, 368, 372, 378, 380, 389, 392, 393, 417, 459, 497, 538, 546, 548, 548, 564, 586, 588, 630, 639, 647, 652, 654, 654, 660, 663, 664, 681, 701, 708, 710, 710, 717, 723, 726, 752, 762, 771, 788, 789, 801, 835, 837, 839, 846, 848, 848, 880, 881, 892, 897, 897, 903, 921, 935, 938, 940, 942, 948, 955, 959, 978, 999]

As we can see, we get the expected results.