《演算法導論》使用 1-based 索引與哨兵,但為配合 C++ STL 慣例,本實作採用 左閉右開區間 [p, r),統一長度計算、避免 +1/-1 易錯的邊界調整。
mergevoid merge(int* A, int p, int q, int r) { // 合併 [p, q) 和 [q, r)
int n1 = q - p, n2 = r - q;
int* L = new int[n1];
int* R = new int[n2];
for (int i = 0; i < n1; ++i) L[i] = A[p + i];
for (int i = 0; i < n2; ++i) R[i] = A[q + i]; // 注意:非 q+i+1
int i = 0, j = 0, k = p;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) A[k++] = L[i++];
else A[k++] = R[j++];
}
while (i < n1) A[k++] = L[i++];
while (j < n2) A[k++] = R[j++];
delete[] L;
delete[] R;
}
merge_sortvoid merge_sort(int* a, int p, int r) { // 呼叫介面:merge_sort(a, 0, len)
if (p < r - 1) { // 區間長度 > 1
int q = p + (r - p) / 2;
merge_sort(a, p, q);
merge_sort(a, q, r); // 同樣用 [q, r)
merge(a, p, q, r);
}
}
int main() {
srand(time(nullptr));
int n;
while (cin >> n) {
int* a = new int[n];
for (int i = 0; i < n; ++i) a[i] = rand() % n;
for (int i = 0; i < n; ++i) printf("%d ", a[i]);
puts("");
merge_sort(a, 0, n);
for (int i = 0; i < n; ++i) printf("%d ", a[i]);
puts("");
delete[] a;
}
return 0;
}
經數萬組隨機測試,輸出結果與 std::sort 完全一致,確認正確性。