English
资源说明：归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
归并操作的过程如下
合并排序（归并排序）是一种基于分治策略的高效排序算法。它的基本思想是将待排序的序列分成两部分，分别对这两部分进行排序，然后将排好序的子序列合并成一个完整的有序序列。这一过程可以递归地应用于每一部分，直到每个子序列只包含一个元素，这时它们都是有序的。接下来，通过比较和合并这些单元素序列来构建更大的有序序列。
1. 分治过程：
- **分割**：将原始序列划分为两个长度大致相等的子序列。
- **解决**：对每个子序列进行归并排序，这意味着继续将子序列分割，直到每个子序列只剩下一个元素，这个阶段是递归的。
- **合并**：将所有已排序的子序列合并成一个大的有序序列。这是通过比较每个子序列的元素并按顺序将它们添加到结果序列中来完成的。
2. 合并操作：
- **初始化**：创建一个与原始序列相同大小的新空间，用于存储合并后的有序序列。
- **指针设置**：设置两个指针，分别指向两个子序列的起始位置。
- **比较与合并**：比较两个指针所指向的元素，将较小的元素添加到合并序列中，并将对应的指针向后移动。
- **重复步骤**：重复上述过程，直到其中一个子序列的所有元素都被添加到合并序列中。
- **复制剩余元素**：将另一个子序列的剩余元素直接复制到合并序列的末尾。
以下是两个JavaScript实现的归并排序示例：
示例1：
```javascript
function mergeSort(items) {
// 基线条件：如果数组长度小于2，直接返回数组
if (items.length < 2) return items;
// 将数组分为左右两半
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle);
// 递归地对左右两半进行排序
var sortedLeft = mergeSort(left),
sortedRight = mergeSort(right);
// 合并排序后的左右两半
var merged = merge(sortedLeft, sortedRight);
// 将合并后的结果替换回原数组
items.splice(0, items.length);
items.splice.apply(items, [0, items.length].concat(merged));
return items;
}
function merge(left, right) {
var result = [];
var il = 0, ir = 0;
// 比较左右两半的元素，将较小的元素添加到结果数组
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
// 添加剩余的元素
return result.concat(left.slice(il)).concat(right.slice(ir));
}
```
示例2：
```javascript
// 这是一个简化的归并排序实现，不包括将结果复制回原数组的部分
function mSort(source, dest, s, t) {
var m;
if (s == t) {
dest[s] = source[s];
} else {
m = Math.floor((s + t) / 2);
mSort(source, dest, s, m);
mSort(source, dest, m + 1, t);
merge(dest, s, m, m + 1, t);
}
}
function merge(dest, s, m, r, t) {
var i, j, k, temp = [];
for (i = s; i <= m; i++) temp[i - s] = dest[i];
for (j = r; j <= t; j++) temp[m - s + j - r + 1] = dest[j];
i = 0;
j = m - s + 1;
k = s;
while (i < m - s + 1 && j < t - m + s + 1) {
if (temp[i] <= temp[j]) {
dest[k++] = temp[i++];
} else {
dest[k++] = temp[j++];
}
}
while (i < m - s + 1) dest[k++] = temp[i++];
while (j < t - m + s + 1) dest[k++] = temp[j++];
}
```
这两个示例展示了如何使用JavaScript实现归并排序。第一个示例使用了`slice()`和`apply()`方法，而第二个示例则更接近于传统的归并排序算法，使用了额外的临时数组来存储合并后的结果。
归并排序的一个重要特性是它具有稳定性，即相等的元素在排序后保持其原有的相对顺序。这种稳定性使得归并排序在处理包含相等元素的列表时特别有用。然而，归并排序的主要缺点是需要额外的空间来存储合并过程中的临时数组，这在处理大量数据时可能成为限制。尽管如此，由于其平均和最坏情况下的时间复杂度均为O(n log n)，归并排序仍然是一个高效的排序算法。
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
