forked from VAR-solutions/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmerge_sort.swift
More file actions
40 lines (34 loc) · 1.19 KB
/
merge_sort.swift
File metadata and controls
40 lines (34 loc) · 1.19 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Author: Nagendra Singh
func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
guard array.count > 1 else { return array }
let middleIndex = array.count / 2
let leftArray = mergeSort(Array(array[0..<middleIndex]))
let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
return merge(leftPile: leftArray, rightPile: rightArray)
}
func merge<T: Comparable>(leftPile: [T], rightPile: [T]) -> [T] {
var leftIndex = 0
var rightIndex = 0
var orderedPile: [T] = []
if orderedPile.capacity < leftPile.count + rightPile.count {
orderedPile.reserveCapacity(leftPile.count + rightPile.count)
}
while true {
guard leftIndex < leftPile.endIndex else {
orderedPile.append(contentsOf: rightPile[rightIndex..<rightPile.endIndex])
break
}
guard rightIndex < rightPile.endIndex else {
orderedPile.append(contentsOf: leftPile[leftIndex..<leftPile.endIndex])
break
}
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
} else {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
}
return orderedPile
}