合并排序(Merge Sort)算法是非常通用的排序算法,是稳定排序,即便在最差的情况下也还有 O(nlogn) 的时间复杂度。
合并排序法(Merge Sort)
合并排序法的概念
合并排序法是最典型的分治(Divide and Conquer)算法,将一整个串行分割成一个个元素,再两两一组依照元素大小填入至新的空间中来合并成新的,并且已经排序好的串行。
合并排序法的过程
假设现在有个数组数据,内容如下:
索引 0 1 2 3 4 5 6 7 8 9 数值 69 81 30 38 9 2 47 61 32 79
要如何将它递增排列呢?
首先将数组对半切成:
索引 0 1 2 3 4 | 5 6 7 8 9 数值 69 81 30 38 9 | 2 47 61 32 79
再对半切成:
索引 0 1 | 2 3 4 || 5 6 | 7 8 9 数值 69 81 | 30 38 9 || 2 47 | 61 32 79
再对半切成:
索引 0 | 1 || 2 | 3 4 ||| 5 | 6 || 7 | 8 9 数值 69 | 81 || 30 | 38 9 ||| 2 | 47 || 61 | 32 79
再对半切成:
索引 0 || 1 ||| 2 || 3 | 4 |||| 5 || 6 ||| 7 || 8 | 9 数值 69 || 81 ||| 30 || 38 | 9 |||| 2 || 47 ||| 61 || 32 | 79
已经不能再切了,即可开始合并,一边合并一边把元素照顺序排好:
索引 0 | 1 || 2 | 3 4 ||| 5 | 6 || 7 | 8 9
数值 69 | 81 || 30 | 9 38 ||| 2 | 47 || 61 | 32 79
→───← →───←
继续合并:
索引 0 1 | 2 3 4 || 5 6 | 7 8 9
数值 69 81 | 9 30 38 || 2 47 | 32 61 79
→────← →────────← →───← →────────←
继续合并:
索引 0 1 2 3 4 | 5 6 7 8 9
数值 9 30 38 69 81 | 2 32 47 61 79
→─────────────────← →─────────────────←
继续合并:
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
→────────────────────────────────────────←
合并完成,也排序完成了!
以上过程看起来十分直觉。程序实作时需要使用额外的空间来进行一边合并一边排序的动作。
合并排序法的程序实作
/// 合并排序法(递增),使用递归。此为用来递归调用的函数。
pub fn merge_sort_recursively(array: &mut [i32], buffer: &mut [i32], start: usize, end: usize) {
if end <= start {
return;
}
let middle = start + ((end - start) >> 1);
let mut ls = start;
let le = middle;
let mut rs = middle + 1;
let re = end;
merge_sort_recursively(array, buffer, ls, le);
merge_sort_recursively(array, buffer, rs, re);
let mut p = start;
while ls <= le && rs <= re {
if array[ls] <= array[rs] {
buffer[p] = array[ls];
ls += 1;
} else {
buffer[p] = array[rs];
rs += 1;
}
p += 1;
}
while ls <= le {
buffer[p] = array[ls];
ls += 1;
p += 1;
}
while rs <= re {
buffer[p] = array[rs];
rs += 1;
p += 1;
}
array[start..=end].copy_from_slice(&buffer[start..=end]);
}
/// 合并排序法(递增),使用递归。
pub fn merge_sort(array: &mut [i32]) {
let length = array.len();
let mut buffer = vec![0; length];
merge_sort_recursively(array, &mut buffer, 0, length - 1);
}
/// 合并排序法(递减),使用递归。此为用来递归调用的函数。
pub fn merge_sort_desc_recursively(
array: &mut [i32],
buffer: &mut [i32],
start: usize,
end: usize,
) {
if end <= start {
return;
}
let middle = start + ((end - start) >> 1);
let mut ls = start;
let le = middle;
let mut rs = middle + 1;
let re = end;
merge_sort_desc_recursively(array, buffer, ls, le);
merge_sort_desc_recursively(array, buffer, rs, re);
let mut p = start;
while ls <= le && rs <= re {
if array[ls] >= array[rs] {
buffer[p] = array[ls];
ls += 1;
} else {
buffer[p] = array[rs];
rs += 1;
}
p += 1;
}
while ls <= le {
buffer[p] = array[ls];
ls += 1;
p += 1;
}
while rs <= re {
buffer[p] = array[rs];
rs += 1;
p += 1;
}
array[start..=end].copy_from_slice(&buffer[start..=end]);
}
/// 合并排序法(递减),使用递归。
pub fn merge_sort_desc(array: &mut [i32]) {
let length = array.len();
let mut buffer = vec![0; length];
merge_sort_desc_recursively(array, &mut buffer, 0, length - 1);
}
>> 1 等同于「除以 2 取整数」,先减后加是为了避免直接计算 end + start 可能会溢出(超过无号整数的表示范围,而使得程序 panic)。
/**
* 合并排序法(递增),使用递归。此为用来递归调用的函数。
*/
public static void mergeSortRecursively(final int[] array, final int[] buffer, final int start, final int end) {
if (end <= start) {
return;
}
final int middle = (end + start) >>> 1;
int ls = start;
final int le = middle;
int rs = middle + 1;
final int re = end;
mergeSortRecursively(array, buffer, ls, le);
mergeSortRecursively(array, buffer, rs, re);
int p = start;
while (ls <= le && rs <= re) {
buffer[p++] = array[ls] <= array[rs] ? array[ls++] : array[rs++];
}
while (ls <= le) {
buffer[p++] = array[ls++];
}
while (rs <= re) {
buffer[p++] = array[rs++];
}
System.arraycopy(buffer, start, array, start, end - start + 1);
}
/**
* 合并排序法(递增),使用递归。
*/
public static void mergeSort(final int[] array) {
final int[] buffer = new int[array.length];
mergeSortRecursively(array, buffer, 0, array.length - 1);
}
/**
* 合并排序法(递减),使用递归。此为用来递归调用的函数。
*/
public static void mergeSortDescRecursively(final int[] array, final int[] buffer, final int start, final int end) {
if (end <= start) {
return;
}
final int middle = (end + start) >>> 1;
int ls = start;
final int le = middle;
int rs = middle + 1;
final int re = end;
mergeSortDescRecursively(array, buffer, ls, le);
mergeSortDescRecursively(array, buffer, rs, re);
int p = start;
while (ls <= le && rs <= re) {
buffer[p++] = array[ls] >= array[rs] ? array[ls++] : array[rs++];
}
while (ls <= le) {
buffer[p++] = array[ls++];
}
while (rs <= re) {
buffer[p++] = array[rs++];
}
System.arraycopy(buffer, start, array, start, end - start + 1);
}
/**
* 合并排序法(递减),使用递归。
*/
public static void mergeSortDesc(final int[] array) {
final int[] buffer = new int[array.length];
mergeSortDescRecursively(array, buffer, 0, array.length - 1);
}
>>> 1 等同于「除以 2 取整数」,利用无号右位移(unsigned right shift)还可以避免 end + start 溢出时导致结果错误(超过有号正整数的表示范围,而变成负数)。
/**
* 合并排序法(递增),使用递归。此为用来递归调用的函数。
*/
function mergeSortRecursively(array: number[], buffer: number[], start: number, end: number) {
if (end <= start) {
return;
}
const middle = start + ((end - start) >> 1);
let ls = start;
const le = middle;
let rs = middle + 1;
const re = end;
mergeSortRecursively(array, buffer, ls, le);
mergeSortRecursively(array, buffer, rs, re);
let p = start;
while (ls <= le && rs <= re) {
buffer[p] = array[ls] <= array[rs] ? array[ls++] : array[rs++];
p += 1;
}
while (ls <= le) {
buffer[p] = array[ls];
p += 1;
ls += 1;
}
while (rs <= re) {
buffer[p] = array[rs];
p += 1;
rs += 1;
}
for (let i = start;i <= end;++i) {
array[i] = buffer[i];
}
}
/**
* 合并排序法(递增),使用递归。
*/
function mergeSort(array: number[]) {
const buffer = new Array<number>(array.length);
mergeSortRecursively(array, buffer, 0, array.length - 1);
}
/**
* 合并排序法(递减),使用递归。此为用来递归调用的函数。
*/
function mergeSortDescRecursively(array: number[], buffer: number[], start: number, end: number) {
if (end <= start) {
return;
}
const middle = start + ((end - start) >> 1);
let ls = start;
const le = middle;
let rs = middle + 1;
const re = end;
mergeSortDescRecursively(array, buffer, ls, le);
mergeSortDescRecursively(array, buffer, rs, re);
let p = start;
while (ls <= le && rs <= re) {
buffer[p] = array[ls] >= array[rs] ? array[ls++] : array[rs++];
p += 1;
}
while (ls <= le) {
buffer[p] = array[ls];
p += 1;
ls += 1;
}
while (rs <= re) {
buffer[p] = array[rs];
p += 1;
rs += 1;
}
for (let i = start;i <= end;++i) {
array[i] = buffer[i];
}
}
/**
* 合并排序法(递减),使用递归。
*/
function mergeSortDesc(array: number[]) {
const buffer = new Array<number>(array.length);
mergeSortDescRecursively(array, buffer, 0, array.length - 1);
}
>> 1 等同于「除以 2 取整数」,先减后加是为了避免直接计算 end + start 可能会超过 232 - 1,若是超过,JavaScript 内置的 32-bit 整数字移功能也就无效了。不过这边其实也可以写成 (end + start) >>> 1,>>> 1 也是等同于「除以 2 取整数」,但利用无号右位移(unsigned right shift)还可以避免 end + start 超过 231 - 1 时进行有号位移(signed shift)后会变成负数的问题。在数组长度不超过 231 的情况下,以上两种写法都能算出正确的结果。不过 JavaScript 的数组最大长度是 232 - 1,如果数组长度超过 231,end - start 有可能会超过 231 - 1,end + start 也有可能会超过 232 - 1,此时要写成 start + ((end - start) >>> 1) 才不会算错。
// 合并排序法(递增),使用递归。此为用来递归调用的函数。
func MergeSortRecursively(array []int, buffer []int, start int, end int) {
if end <= start {
return
}
middle := int(uint(end+start) >> 1)
ls := start
le := middle
rs := middle + 1
re := end
MergeSortRecursively(array, buffer, ls, le)
MergeSortRecursively(array, buffer, rs, re)
p := start
for ls <= le && rs <= re {
if array[ls] <= array[rs] {
buffer[p] = array[ls]
ls += 1
} else {
buffer[p] = array[rs]
rs += 1
}
p += 1
}
for ls <= le {
buffer[p] = array[ls]
ls += 1
p += 1
}
for rs <= re {
buffer[p] = array[rs]
rs += 1
p += 1
}
copy(array[start:(end+1)], buffer[start:(end+1)])
}
// 合并排序法(递增),使用递归。
func MergeSort(array []int) {
length := len(array)
buffer := make([]int, length)
MergeSortRecursively(array, buffer, 0, length-1)
}
// 合并排序法(递减),使用递归。此为用来递归调用的函数。
func MergeSortDescRecursively(array []int, buffer []int, start int, end int) {
length := end - start + 1
if length < 2 {
return
}
middle := int(uint(end+start) >> 1)
ls := start
le := middle
rs := middle + 1
re := end
MergeSortDescRecursively(array, buffer, ls, le)
MergeSortDescRecursively(array, buffer, rs, re)
p := start
for ls <= le && rs <= re {
if array[ls] >= array[rs] {
buffer[p] = array[ls]
ls += 1
} else {
buffer[p] = array[rs]
rs += 1
}
p += 1
}
for ls <= le {
buffer[p] = array[ls]
ls += 1
p += 1
}
for rs <= re {
buffer[p] = array[rs]
rs += 1
p += 1
}
copy(array[start:(end+1)], buffer[start:(end+1)])
}
// 合并排序法(递减),使用递归。
func MergeSortDesc(array []int) {
length := len(array)
buffer := make([]int, length)
MergeSortDescRecursively(array, buffer, 0, length-1)
}
>> 1 等同于「除以 2 取整数」,把 end+start 的结果先转成无号整数(unsigned integer)是因为它可能会溢出(超过有号正整数的表示范围,而变成负数)。
在实作程序的时候,应该要避免使用递归(Recursive)的结构,因为递归需要不断地重新建构函数的堆栈空间,硬件资源的负担会比较大,且若是递归层数过多还会导致堆栈溢出(Stack Overflow)。所以比较好的做法还是在一个函数内以循环迭代的方式来完成。
为了化简递归转迭代结构时的问题,在这里不采取从中间开始分割的方式,而是直接跳过分割的动作,从合并开始进行。在观察合并排序法的分割过程后,其实不难发现完整的子数组的长度,合并过后的长度都会再乘上 2,且即便是未达 2 的乘幂长度的数组,也能进行合并的动作。也就是说,分割的动作其实并非必要,可以直接从前端开始直接合并 2 的乘幂个元素,先从 1 (20)个元素两两开始合并,再从 2 (21)个元素两两开始合并,再从 4 (22)个元素两两开始合并,再从 8 (23)个元素两两开始合并,依此类推。因此可以写出如下的迭代版合并排序法:
/// 合并排序法(递增),使用循环来迭代。
pub fn merge_sort(array: &mut [i32]) {
let length = array.len();
let length_dec = length - 1;
let mut buffer = vec![0; length];
let mut width = 1;
while width < length {
let double_width = width << 1;
let e = length_dec - width;
for start in (0..=e).step_by(double_width) {
let mut end = start + double_width - 1;
if end > length_dec {
end = length_dec;
}
let middle = start + width;
let mut ls = start;
let le = middle - 1;
let mut rs = middle;
let re = end;
let mut p = start;
while ls <= le && rs <= re {
if array[ls] <= array[rs] {
buffer[p] = array[ls];
ls += 1;
} else {
buffer[p] = array[rs];
rs += 1;
}
p += 1;
}
while ls <= le {
buffer[p] = array[ls];
ls += 1;
p += 1;
}
while rs <= re {
buffer[p] = array[rs];
rs += 1;
p += 1;
}
array[start..=end].copy_from_slice(&buffer[start..=end]);
}
width = double_width;
}
}
/// 合并排序法(递减),使用循环来迭代。
pub fn merge_sort_desc(array: &mut [i32]) {
let length = array.len();
let length_dec = length - 1;
let mut buffer = vec![0; length];
let mut width = 1;
while width < length {
let double_width = width << 1;
let e = length_dec - width;
for start in (0..=e).step_by(double_width) {
let mut end = start + double_width - 1;
if end > length_dec {
end = length_dec;
}
let middle = start + width;
let mut ls = start;
let le = middle - 1;
let mut rs = middle;
let re = end;
let mut p = start;
while ls <= le && rs <= re {
if array[ls] >= array[rs] {
buffer[p] = array[ls];
ls += 1;
} else {
buffer[p] = array[rs];
rs += 1;
}
p += 1;
}
while ls <= le {
buffer[p] = array[ls];
ls += 1;
p += 1;
}
while rs <= re {
buffer[p] = array[rs];
rs += 1;
p += 1;
}
array[start..=end].copy_from_slice(&buffer[start..=end]);
}
width = double_width;
}
}
/**
* 合并排序法(递增),使用循环来迭代。
*/
public static void mergeSort(final int[] array) {
final int length = array.length;
final int lengthDec = length - 1;
final int[] buffer = new int[length];
int width = 1;
while (width < length) {
final int doubleWidth = width << 1;
final int e = lengthDec - width;
for (int start = 0; start <= e; start += doubleWidth) {
int end = start + doubleWidth - 1;
if (end > lengthDec) {
end = lengthDec;
}
final int middle = start + width;
int ls = start;
final int le = middle - 1;
int rs = middle;
final int re = end;
int p = start;
while (ls <= le && rs <= re) {
buffer[p++] = array[ls] <= array[rs] ? array[ls++] : array[rs++];
}
while (ls <= le) {
buffer[p++] = array[ls++];
}
while (rs <= re) {
buffer[p++] = array[rs++];
}
System.arraycopy(buffer, start, array, start, end - start + 1);
}
width = doubleWidth;
}
}
/**
* 合并排序法(递减),使用循环来迭代。
*/
public static void mergeSortDesc(final int[] array) {
final int length = array.length;
final int lengthDec = length - 1;
final int[] buffer = new int[length];
int width = 1;
while (width < length) {
final int doubleWidth = width << 1;
final int e = lengthDec - width;
for (int start = 0; start <= e; start += doubleWidth) {
int end = start + doubleWidth - 1;
if (end > lengthDec) {
end = lengthDec;
}
final int middle = start + width;
int ls = start;
final int le = middle - 1;
int rs = middle;
final int re = end;
int p = start;
while (ls <= le && rs <= re) {
buffer[p++] = array[ls] >= array[rs] ? array[ls++] : array[rs++];
}
while (ls <= le) {
buffer[p++] = array[ls++];
}
while (rs <= re) {
buffer[p++] = array[rs++];
}
System.arraycopy(buffer, start, array, start, end - start + 1);
}
width = doubleWidth;
}
}
/**
* 合并排序法(递增),使用循环来迭代。
*/
function mergeSort(array: number[]) {
const length = array.length;
const lengthDec = length - 1;
const buffer = new Array<number>(length);
let width = 1;
while (width < length) {
const doubleWidth = width << 1;
const e = lengthDec - width;
for (let start = 0;start <= e;start += doubleWidth) {
let end = start + doubleWidth - 1;
if (end > lengthDec) {
end = lengthDec;
}
const middle = start + width;
let ls = start;
const le = middle - 1;
let rs = middle;
const re = end;
let p = start;
while (ls <= le && rs <= re) {
buffer[p] = array[ls] <= array[rs] ? array[ls++] : array[rs++];
p += 1;
}
while (ls <= le) {
buffer[p] = array[ls];
p += 1;
ls += 1;
}
while (rs <= re) {
buffer[p] = array[rs];
p += 1;
rs += 1;
}
for (let i = start;i <= end;++i) {
array[i] = buffer[i];
}
}
width = doubleWidth;
}
}
/**
* 合并排序法(递减),使用循环来迭代。
*/
function mergeSortDesc(array: number[]) {
const length = array.length;
const lengthDec = length - 1;
const buffer = new Array<number>(length);
let width = 1;
while (width < length) {
const doubleWidth = width << 1;
const e = lengthDec - width;
for (let start = 0;start <= e;start += doubleWidth) {
let end = start + doubleWidth - 1;
if (end > lengthDec) {
end = lengthDec;
}
const middle = start + width;
let ls = start;
const le = middle - 1;
let rs = middle;
const re = end;
let p = start;
while (ls <= le && rs <= re) {
buffer[p] = array[ls] >= array[rs] ? array[ls++] : array[rs++];
p += 1;
}
while (ls <= le) {
buffer[p] = array[ls];
p += 1;
ls += 1;
}
while (rs <= re) {
buffer[p] = array[rs];
p += 1;
rs += 1;
}
for (let i = start;i <= end;++i) {
array[i] = buffer[i];
}
}
width = doubleWidth;
}
}
// 合并排序法(递增),使用循环来迭代。
func MergeSort(array []int) {
length := len(array)
lengthDec := length - 1
buffer := make([]int, length)
width := 1
for width < length {
doubleWidth := width << 1
e := lengthDec - width
for start := 0; start <= e; start += doubleWidth {
end := start + doubleWidth - 1
if end > lengthDec {
end = lengthDec
}
middle := start + width
ls := start
le := middle - 1
rs := middle
re := end
p := start
for ls <= le && rs <= re {
if array[ls] <= array[rs] {
buffer[p] = array[ls]
ls += 1
} else {
buffer[p] = array[rs]
rs += 1
}
p += 1
}
for ls <= le {
buffer[p] = array[ls]
ls += 1
p += 1
}
for rs <= re {
buffer[p] = array[rs]
rs += 1
p += 1
}
copy(array[start:(end+1)], buffer[start:(end+1)])
}
width = doubleWidth
}
}
// 合并排序法(递减),使用循环来迭代。
func MergeSortDesc(array []int) {
length := len(array)
lengthDec := length - 1
buffer := make([]int, length)
width := 1
for width < length {
doubleWidth := width << 1
e := lengthDec - width
for start := 0; start <= e; start += doubleWidth {
end := start + doubleWidth - 1
if end > lengthDec {
end = lengthDec
}
middle := start + width
ls := start
le := middle - 1
rs := middle
re := end
p := start
for ls <= le && rs <= re {
if array[ls] >= array[rs] {
buffer[p] = array[ls]
ls += 1
} else {
buffer[p] = array[rs]
rs += 1
}
p += 1
}
for ls <= le {
buffer[p] = array[ls]
ls += 1
p += 1
}
for rs <= re {
buffer[p] = array[rs]
rs += 1
p += 1
}
copy(array[start:(end+1)], buffer[start:(end+1)])
}
width = doubleWidth
}
}
<< 1 等同于「乘 2」。
合并排序法的复杂度
以 #{{n}}# 来表示要排序的数据笔数。
| 项目 | 值 | 备注 |
|---|---|---|
| 最差时间复杂度 | #{{O(n \log n)}}# | |
| 最佳时间复杂度 | #{{O(n \log n)}}# | |
| 平均时间复杂度 | #{{O(n \log n)}}# | |
| 最差空间复杂度 | #{{O(n)}}# | |
| 是否稳定 | 是 |

