归并排序分两个阶段：
- 第一阶段：分组，假设集合一共有
n个元素，算法将会对集合进行逐层的折半分组，一直到每组只有一个元素为止； - 第二阶段：归并，每个小组内部比较出先后顺序后，小组之间会展开进一步的比较和排序进而合并成一个大足，大组间继续比较和排序并合并成更大的组，反复执行最终所有元素合并成一个有序的集合。
归并包含三步：- 第一步，创建一个长度为两个小集合长度之和的大集合用于存储归并结果；
- 第二步，从左到右逐一比较两个小集合中的元素，把较小的元素优先放入大集合 ；
- 第三步，从另一个还有剩余元素的集合中，把剩余元素按顺序复制到大集合尾部。
复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(n)
Java 代码实现
import java.util.Arrays;
public class MergeSort {
public static void sort(int[] data, int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
sort(data, start, middle);
sort(data, middle + 1, end);
merge(data, start, middle, end);
}
}
private static void merge(int[] data, int start, int middle, int end) {
int[] temp = new int[end - start + 1];
int p1 = start;
int p2 = middle + 1;
int p = 0;
while (p1 <= middle && p2 <= end) {
if (data[p1] <= data[p2]) {
temp[p] = data[p1++];
} else {
temp[p] = data[p2++];
}
p++;
}
while (p1 <= middle) {
temp[p++] = data[p1++];
}
while (p2 <= end) {
temp[p++] = data[p2++];
}
for (int i = 0; i < temp.length; i++) {
data[i + start] = temp[i];
}
}
public static void main(String[] args) {
int[] data = {34, 24, 93, 1, 32, 98, 18, 39};
sort(data, 0, data.length - 1);
System.out.println(Arrays.toString(data));
}
}
运行结果
[1, 18, 24, 32, 34, 39, 93, 98]
