概念

归并排序(英文:merge sort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。
归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

归并排序算法演示动画

递归法

原理如下(假设序列共有n个元素):

  1. 将序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素
  2. 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
  3. 重复步骤2,直到所有元素排序完毕

迭代法

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

代码实现(java)

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* 归并排序,递归版
*/
public static <E extends Comparable<? super E>> List<E> mergeSort(List<E> m) {
if (m.size() <= 1) {
return m;
}

int middle = m.size() / 2;
List<E> left = m.subList(0, middle);
List<E> right = m.subList(middle, m.size());

right = mergeSort(right);
left = mergeSort(left);
List<E> result = merge(left, right);

return result;
}

public static <E extends Comparable<? super E>> List<E> merge(List<E> left, List<E> right) {
List<E> result = new ArrayList<E>();
Iterator<E> it1 = left.iterator();
Iterator<E> it2 = right.iterator();

E x = it1.next();
E y = it2.next();
while (true) {
// change the direction of this comparison to change the direction
// of the sort
if (x.compareTo(y) <= 0) {
result.add(x);
if (it1.hasNext()) {
x = it1.next();
} else {
result.add(y);
while (it2.hasNext()) {
result.add(it2.next());
}
break;
}
} else {
result.add(y);
if (it2.hasNext()) {
y = it2.next();
} else {
result.add(x);
while (it1.hasNext()) {
result.add(it1.next());
}
break;
}
}
}
return result;
}

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* 归并排序,迭代版
*/
public static void mergeSort(int[] nums) {
int len = nums.length;
int[] result = new int[len];
int block, start;

for (block = 1; block < len * 2; block *= 2) {
for (start = 0; start < len; start += 2 * block) {
int low = start;
int mid = (start + block) < len ? (start + block) : len;
int high = (start + 2 * block) < len ? (start + 2 * block) : len;
// 两个块的起始下标及结束下标
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
// 开始对两个block进行归并排序
while (start1 < end1 && start2 < end2) {
result[low++] = nums[start1] < nums[start2] ? nums[start1++] : nums[start2++];
}
while (start1 < end1) {
result[low++] = nums[start1++];
}
while (start2 < end2) {
result[low++] = nums[start2++];
}
}
int[] temp = nums;
nums = result;
result = temp;
}
result = nums;
}

算法复杂度分析

比较操作的次数介于(n*logn)/2(n log n)/2和n*logn?n+1。 赋值操作的次数是 n*logn。归并算法的空间复杂度为:O(n)。

参考文章