Merge Sort
Last updated
Last updated
Algorithms โฉ Sorting โฉ merge sort
// merge sort
extension Array where Element: Comparable {
typealias Comparison = (Element, Element) -> Bool
// โญ๏ธ array.split()
// (split into 2 subarrays)
private func split() -> ([Element], [Element]) {
let half = count / 2
return (Array(self[..<half]), Array(self[half...]))
}
// โญ๏ธ array.merge(with: other)
// โ๏ธ precondition: 2 arrays must be ordered
private func merge(with array: [Element], comparison: Comparison) -> [Element] {
var result = [Element]()
var i = 0, j = 0 // index for smallest element in each array
// merge phase 1:
// compare smallest element from 2 arrays (both NOT empty)
while i < self.count, j < array.count {
// get smallest element in each array
let s1 = self[i]
let s2 = array[j]
// compare 2 smallest elements
if comparison(s1, s2) {
result.append(s1)
i += 1
} else {
result.append(s2)
j += 1
}
}
// merge phase 2:
// append rest elements (at least one of the arrays is empty)
result += self[i...]
result += array[j...]
return result
}
// โญ๏ธ array.mergeSort(by:)
// default comparison function โ โญโญ๏ธโฎ
func mergeSort(by op: Comparison = (<) ) -> [Element] {
////////// โญ๏ธ base case //////////
guard count > 1 else { return self }
////////// โญ๏ธ recursive case //////////
// โญ๏ธ 1. split into 2 subarrays
var (arr1, arr2) = self.split()
// โญ๏ธ 2. sort subarrays (recursively)
arr1 = arr1.mergeSort(by: op)
arr2 = arr2.mergeSort(by: op)
// โญ๏ธ 3. merge subarrays
return arr1.merge(with: arr2, comparison: op)
}
}
๐็ฏไพ๏ผ
// test merge sort
let arr = [15, 1, 5, 8, 9, 10, 2, 50, 40, 3, 2, 9, 10, 7, 33, 34]
arr.mergeSort() // 1, 2, 2, 3 ...
arr.mergeSort(by: >) // 50, 40, 34, ...
the sorted(by:)
function is actually 2 different functions.
one requires Comparable
and uses <
internally.
the other lets you specify the sorting logic directly (Comparable
conformance not required).
... this convenience sorting by keyPath
would still require 2 functions.
๐ Reference default comparison function as a function parameter
โญ๏ธ ๆณจๆ๏ผ
่ฆๅฐ <
่จญ็บๅฝๆธๅๆธ้ ่จญๅผๆ๏ผๅฟ
้ ไฝฟ็จ ()
ๅฐๆฌ่๏ผๅฆๅๆ็ข็้ฏ่ชคโ๏ธ
// โญ๏ธ default comparison โฎ
func mergeSort(by op: Comparison = (<) )
๐ Reference default comparison function as a function parameter
if you need to sort huge data, you have to prepare an additional space of the same size, which is a weak point of merge sort. This is one of main reasons why it is not used as frequently as the quick sort algorithm ...
๐ ๅ่๏ผFirst Course in Algorithms Through Puzzles (2019), 3.3 Sorting
Swift โฉ Array โฉ ArraySlice
can sort Array.
arr.split(where:) splits array into subarrays by comparing consecutive elements.