归并排序
- 第一个工业级别的算法
- 归并排序没有办法就地排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function mergeSort(ary) {
if (ary.length < 2) {
return ary.slice()
}
var mid = Math.floor(ary.length / 2)
var left = mergeSort(ary.slice(0, mid))
var right = mergeSort(ary.slice(mid))
var result = []
while(left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
result.push(...left, ...right)
return result
}