This article is a translation of Swift Algorithm Club.
Swift Algorithm Club is an open source project produced by Raywenderlich.com to realize algorithms and data structures by Swift. Currently, there are 18000+⭐️ on GitHub. I have made a brief statistics, and there are about 100 algorithms and data structures. It’s basically a good resource for iOSer learning algorithms and data structures.
🐙andyRon/ swiftalgorithmclubCN is my project of learning and translating for Swift Algorithm Club. Due to the limited capacity, if you find any errors or improper translation, please correct them. Welcome to Pull Request. Also welcome interested, have time partners to participate in translation and learning 🤓. Of course, we welcome ⭐️, 🤩🤩 ️ ⭐ ⭐.
A translation of this article and the code can be found at 🐙swiftalgorithmclubcn/Merge Sort
There are already tutorial articles on this topic
Target: Sort the array from low to high (or high to low)
Merge sort, invented by John von Neumann in 1945, is an efficient algorithm with best, worst, and average time complexity of O(n log n).
Merge sort uses a divideandconquer approach, breaking a big problem into smaller ones and solving them. Merge sort algorithm can be divided into split and merge.
Suppose you need to sort an array of length N in the correct order. The merging sort algorithm works as follows:
 Put the numbers in the unsorted heap.
 Divide the heap into two parts. So now we have two unsorted stacks of numbers.
 Continue to splitTwo unsorted stacks of numbersUntil you can’t split. In the end, you will havenIt’s a heap, and there’s a number in each heap.
 Begin merging the heap by sequential pairing. During each merge, the content is sorted in sort order. This is easy because each individual heap is already sorted.
example
Break up
Suppose you were given an unsorted array of length n: [2,1,5,4,9]. The goal is to keep splitting the heap until you can’t.
First, split the array in half: [2,1] and [5,4,9]. Can you continue to split it? Yes you can!
Focus on the left heap. Split [2,1] into [2] and [1]. Can you continue to split it? Can’t. Check the heap on the right.
Split [5,4,9] into [5] and [4,9]. As expected, [5] can no longer be split, but [4,9] can be split into [4] and [9].
The final result of splitting is: [2] [1] [5] [4] [9]. Note that each heap contains only one element.
merge
Now that you have split the array, you should merge and sort the split heap. Remember, the idea is to solve many small problems rather than one big one. For each merge iteration, you must focus on merging one heap with another.
Heap for [2] [1] [5] [4] [9], the first merger is the result of [1, 2] and [4, 5] and [9]. Since [9] is single, no heap is merged with it during the merge.
The next time will merge [1,2] and [4,5]. As a result [1,2,4,5], again due to the location of [9] single no need to merge.
Only two heaps [1,2,4,5] and [9] are left, and the collated array is [1,2,4,5,9].
Topdown implementation (recursive method)
Swift implementation of merge sort:
func mergeSort(_ array: [Int]) > [Int] {
guard array.count > 1 else { return array } / / 1
let middleIndex = array.count / 2 / / 2
let leftArray = mergeSort(Array(array[0..<middleIndex])) / / 3
let rightArray = mergeSort(Array(array[middleIndex..<array.count])) / / 4
return merge(leftPile: leftArray, rightPile: rightArray) / / 5
}
Copy the code
Stepbystep description of the code:

If the array is empty or contains a single element, you can’t split it into smaller parts, just return the array.

Find the intermediate index.

Use the intermediate index from the previous step to recursively split the left side of the array.

In addition, the right side of the array is recursively split.

Finally, merge all the values together to make sure it is always sorted.
Here is the merging algorithm:
func merge(leftPile: [Int], rightPile: [Int]) > [Int] {
/ / 1
var leftIndex = 0
var rightIndex = 0
/ / 2
var orderedPile = [Int] ()/ / 3
while leftIndex < leftPile.count && rightIndex < rightPile.count {
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
} else if leftPile[leftIndex] > rightPile[rightIndex] {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
} else {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
orderedPile.append(rightPile[rightIndex])
rightIndex += 1}}/ / 4
while leftIndex < leftPile.count {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
}
while rightIndex < rightPile.count {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
return orderedPile
}
Copy the code
This method may seem scary, but it’s very simple:

When merging, you need two indexes to track the progress of the two arrays.

This is the merged array. It is now empty, but you will build it by adding elements from other arrays in the steps below.

This while loop compares the left and right elements and adds them to orderedPile, while ensuring that the results remain ordered.

If the previous while loop completes, it means that the contents of either leftPile or rightPile have been fully merged into orderedPile. At this point, you no longer need to compare. Simply add the remaining contents of the remaining array in turn to orderedPile.
Example of how the merge() function works. Suppose we have two piles: leftPile = [1,7,8] and rightPile = [3,6,9]. Note that both heaps are sorted separately — merge sort is always the case. The following steps combine them into a larger sorted heap:
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ ]
l r
Copy the code
The left index (denoted here as L) points to the first item 1 in the left heap. On the right, the index r points to 3. Therefore, the first item we add to orderedPile is 1. We also move the left index L to the next item.
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1 ]
>l r
Copy the code
Now L is pointing at 7 but R is still at 3. We add the smallest item, 3, to the ordered heap. Here’s what’s going on:
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3 ]
l >r
Copy the code
Repeat the above process. In each step, we select the smallest item from leftPile or rightPile and add the item to orderedPile:
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6 ]
l >r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7 ]
>l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7, 8 ]
>l r
Copy the code
Now, there are no more items in the left heap. We just add the remaining items from the heap on the right, and we’re done. The merged heap is [1,3,6,7,8,9].
Note that this algorithm is very simple: it moves left to right through the two heaps and selects the smallest item at each step. This works because we guarantee that each heap is sorted.
I found a graphic GIF of merge sort for topdown execution, source
Bottomup implementation (iteration)
The implementation of the merge sort algorithm you’ve seen so far is called a “topdown” approach because it first splits the array into smaller heaps and then merges them. When sorting an array (as opposed to a linked list), you can actually skip the split step and start merging the array elements immediately. This is called the “bottomup” approach.
Here is a complete bottomup implementation in Swift:
func mergeSortBottomUp<T>(_ a: [T], _ isOrderedBefore: (T, T) > Bool)  > [T] {
let n = a.count
var z = [a, a] / / 1
var d = 0
var width = 1
while width < n { / / 2
var i = 0
while i < n { / / 3
var j = i
var l = i
var r = i + width
let lmax = min(l + width, n)
let rmax = min(r + width, n)
while l < lmax && r < rmax { / / 4
if isOrderedBefore(z[d][l], z[d][r]) {
z[1  d][j] = z[d][l]
l += 1
} else {
z[1  d][j] = z[d][r]
r += 1
}
j += 1
}
while l < lmax {
z[1  d][j] = z[d][l]
j += 1
l += 1
}
while r < rmax {
z[1  d][j] = z[d][r]
j += 1
r += 1
}
i += width*2
}
width *= 2
d = 1  d / / 5
}
return z[d]
}
Copy the code
It looks more daunting than the topdown version, but notice that the body contains the same three while loops as merge().
Important points to note:

The merge sort algorithm requires a temporary working array because you cannot merge the left and right heaps and overwrite their contents at the same time. Since it is wasteful to allocate a new array for each merge, we use two working arrays and we will switch between them using the value of D, which is either 0 or 1. The array z[d] is used for reading and z[1d] is used for writing. This is called double buffering.

Conceptually, the bottomup version works in the same way as the topdown version. First, it merges small heaps of each element, then it merges two elements per heap, then four elements per heap, and so on. The size of the heap is given by width. Initially, width is 1, but at the end of each iteration of the loop, we multiply it by 2, so the outer loop determines the size of the heap to merge, and the subarrays to merge become larger at each step.

The inner loop runs through the heap and merges each pair of heaps into a larger heap. The result is written in the array given by z[1d].

This is the same logic as the topdown version. The main difference is that we use double buffering, so the value is read from z[d] and written to z[1d]. It also uses the isOrderedBefore function to compare elements rather than just <, so this merge sort algorithm is universal and you can use it to sort any type of object.

At this point, the heap of the size width of array Z [d] has been merged into the larger size width * 2 of array Z [1d]. Here, we swap the active array so that in the next step we will read from the new heap we just created.
This function is generic, so you can use it to sort any type of object you want, as long as you provide a proper isOrderedBefore closure to compare elements.
Examples of how to use it:
let array = [2.1.5.4.9]
mergeSortBottomUp(array, <) // [1, 2, 4, 5, 9]
Copy the code
For iteration merge sort, I found a graph to show the source
performance
The speed of the merge sort algorithm depends on the size of the array it needs to sort. The larger the array, the more work it needs to do.
Whether the initial array is sorted or not doesn’t affect the speed of the merge sort algorithm, because you will do the same number of splits and comparisons regardless of the initial order of the elements.
Therefore, the time complexity of the best, worst and average cases will always be O(n log n).
One drawback of the merge sort algorithm is that it requires a temporary “working” array of the same size as the array being sorted. It does not sort in place, like quicksort for example.
Most implementations of merge sort algorithms are stable sorts. This means that array elements with the same sort key will remain in the same order relative to each other after sorting. This is not important for simple values like numbers or strings, but when sorting more complex objects, it can be problematic if the sorting is not stable.
A sorting algorithm is stable if the elements are the same and the relative order remains the same. Stable sort: insert sort, count sort, merge sort, radix sort and so on, see stable sort.
Further reading
Merge sort wikipedia
Merge sort Chinese Wikipedia
By Kelvin Lau. Additions, Matthijs Hollemans Translated by Andy Ron Proofread by Andy Ron