如何在JavaScript中实现合并排序？
合并排序
合并排序是分治式排序算法的一个示例。合并排序的输入是一些元素的数组，通常需要按照从最小到最大的顺序排列。
合并排序中的步骤
合并排序将数组分成两个子数组，然后将每个数组又分成另外两个数组，依此类推，直到剩下一堆单元素数组为止。例如，在以下示例中，数组[4,7,5,9,1,3,8,2]分成单个数组元素，例如[4]，[7]，[5]，[9]，[1]，[3]，[8]，[2]。
它以比较和连接两个数组的方式开始比较数组。在以下示例中，它一次比较两个数组，即[4]，[7]进行比较和级联，然后[5]，[9]进行比较和级联，依此类推，从而使数组[4,7]，[形成[5，9]，[1，3]，[2，8]。
它遵循相同的方法，即比较两个两个数组并将它们连接起来以形成两个数组。在下面的示例中，将[4,7]和[5,9]进行比较和连接，以得到一个数组为[4,5,7,9]，其他两个数组也一样，形成一个数组为[1，2,3,8]。
此处适用的相同规则是，其余两个数组进行比较和连接以得到最终数组为[1,2,3,4,5,7,8,9]。
示例
<html>
<body>
<script>
function mSort (array) {
if (array.length === 1) {
return array // return once we hit an array with a single item
}
const middle = Math.floor(array.length / 2) // get the middle item of the array rounded down
const left = array.slice(0, middle) // items on the left side
const right = array.slice(middle) // items on the right side
document.write(middle);
return merge(
mSort(left),
mSort(right)
)
}
//逐项比较数组，并返回连接结果
function merge (left, right) {
let result = []
let leftIndex = 0
let rightIndex = 0
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex])
leftIndex++
document.write("</br>");
} else {
result.push(right[rightIndex])
rightIndex++
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))
}
const list = [4,7,5,9,1,3,8,2]
document.write(mSort(list));
</script>
</body>
</html>输出结果
1,2,3,4,5,7,8,9