概念
將陣列切半直至一數，再兩兩比較將小者先排入新序列，此動作稱為合併，重複動做至剩一序列。
實作 (bottom-up)
由於使用botton-up 可以直接使用陣列，所以不必再將陣列切成一塊，只需合併。
- 建立指標目的是間接性修改資料，如下：a指向arr陣列，而b為排列後代換的。為什麼不直接替換的原因是：欲比較兩序列中左值若大於右值，交換就會破壞合併時的比較。
- 第一層迴圈是枚舉長度，從序列n個，藉序列大小乘二，至序列只有一個。以此模擬合併後的序列。
- 第二層迴圈是遍歷兩欲比較序列，當中以指標設置欲比較序列中的數值，start 為左方序列首，mid 為左序列尾、右序列首，high 為右序列尾，start1、start2、end1、end2紀錄當下比較位置、範圍限制。
- while迴圈是將比較結果存入b，模擬比較後放入。
- 將值替換。
//參考自維基
//https://gist.githubusercontent.com/hsuan1117/a0aac51cd40ca40260fddebfda79c243/raw/37a16ac614cea62b2880088123226f606f252e57/MergeSort%2520(Wiki).cpp
void merge_sort(int arr[], int len) {
int *a = arr;
int *b = new int[len];
for (int i = 1; i < len; i *= 2) {
for (int start = 0; start < len; start += i*2) {
int low = start,
mid = min(start + i, len),
high = cmp(start + i *2, len),
k = low,
start1 = low, end1 = mid,
start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] =
a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
swap(a,b);
}
if (a != arr) {
for (int i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
delete[] b;
}