归并算法（Merge Algorithm）是一种在计算机科学中广泛使用的算法，特别在排序领域中有着重要的地位。归并操作主要用于将两个或多个有序的子序列合并成一个新的有序序列。
归并排序（Merge Sort）是一个基于归并算法的排序方法，它采用了分治（Divide and Conquer）策略：
分治阶段： 将待排序的序列不断地二等分，直至每个子序列只剩下一个元素，这些单元素的子序列自然都是有序的。
合并阶段： 使用归并操作将相邻的有序子序列合并成一个更大的有序子序列，这一过程递归地进行，直到最后得到一个完全有序的序列。
归并排序的具体步骤包括：
将序列划分为两个子序列，每个子序列可以进一步递归地进行归并排序。
合并两个已排序的子序列：创建一个新的临时数组（或使用额外的空间），从两个子序列的头部开始比较元素，把较小的元素放入临时数组，直到某一个子序列为空，然后将另一个子序列剩余的元素全部复制到临时数组中。
最终将临时数组的内容复制回原数组，完成合并。
以下是一个简单的Java实现归并排序的例子：
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 递归地对左右两半进行归并排序
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并两个有序的子数组
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
// 合并两个子数组，将较小的元素放入temp数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 将剩余的元素填充进temp数组
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 将temp数组中的元素复制回原数组
for (i = left; i <= right; i++) {
arr[i] = temp[i - left];
}
}
// 示例：调用归并排序函数
public static void sort(int[] arr) {
mergeSort(arr, 0, arr.length - 1);
}
}此算法的时间复杂度为O(n log n)，空间复杂度为O(n)，其中n代表待排序数组的元素个数。尽管空间消耗较大，但由于其稳定性以及对于大数据集的良好性能，归并排序在许多场合下具有很高的实用价值。
原文链接: https://www.yukx.com/arithmetic/article/details/2473.html 优科学习网归并排序算法
