合併排序(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::with_capacity(length);
unsafe {
buffer.set_len(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::with_capacity(length);
unsafe {
buffer.set_len(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, length);
}
/**
* 合併排序法(遞增)，使用遞迴。
*/
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, length);
}
/**
* 合併排序法(遞減)，使用遞迴。
*/
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;
ls += 1;
rs += 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;
ls += 1;
rs += 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)後會變成負數的問題，並且又因JavaScript的陣列最大長度是231 - 1，所以end + start在正常情況下並不會超過232 - 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::with_capacity(length);
unsafe {
buffer.set_len(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::with_capacity(length);
unsafe {
buffer.set_len(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 <= rs && 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 <= rs && 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;
ls += 1;
rs += 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;
ls += 1;
rs += 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)}}# | |
| 是否穩定 | 是 |