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.