归并排序

arr = [5, 4, 3, 2, 1]

const mergeSort = (arr) => {
	if (arr.length < 2) return arr
	const mid = Math.floor(arr.length / 2)
	const left = arr.slice(0, mid)
	const right = arr.slice(mid)
	return merge(mergeSort(left), mergeSort(right))
}
const merge = (left, right) => {
	const result = []
	while (left.length && right.length) {
		if (left[0] < right[0]) {
			result.push(left.shift())
		} else {
			result.push(right.shift())
		}
	}
	return [...result, ...left, ...right]
}

console.log(mergeSort(arr))




//单函数
function mergeSort(params) {
	if (params.length <= 1) {
		return params
	}
	let mid = Math.floor(params.length / 2)
	let left = params.slice(0, mid)
	let right = params.slice(mid)
	let orderLeft = mergeSort(left)
	let orderRight = mergeSort(right)
	let res = []
	while (orderLeft.length || orderRight.length) {
		if (orderLeft.length && orderRight.length) {
			res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
		} else if (orderLeft.length) {
			res.push(orderLeft.shift())
		} else if (orderRight.length) {
			res.push(orderRight.shift())
		}
	}
	return res
}

console.log(mergeSort([9, 2, 5, 4, 2, 6, 7, 4, 9, 10]))