归并排序

algorithm

归并排序是采用分治法（Divide and Conquer）的排序算法。

算法原理

JavaScript实现

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
function merge(leftArr, rightArr) {
	let result = [];

	while(leftArr.length > 0 && rightArr.length > 0) {
		if (leftArr[0] <= rightArr[0]) {
			result.push(leftArr.shift());
		} else {
			result.push(rightArr.shift());
		}
	}

	result.push(...leftArr, ...rightArr)

	return result;
}

function mergeSort(arr) {
	if (arr.length <= 1) return arr;

	const middle = arr.length / 2;
	const leftArr = arr.slice(0, middle);
	const rightArr = arr.slice(middle);

	return merge(mergeSort(leftArr), mergeSort(rightArr));
}

mergeSort([13, 24, 0, 99, -1, 55, 4, 9, 2, 0]);

复杂度

参考