實現邏輯
① 將序列每相鄰兩個數字進行歸并操作，形成floor(n/2)個序列，排序后每個序列包含兩個元素
② 將上述序列再次歸并，形成floor(n/4)個序列，每個序列包含四個元素
③ 重復步驟②，直到所有元素排序完畢

void print_array(int a[], int n){for (int i = 0; i < n; ++i){cout << a[i] << " ";}cout << endl;
}/************************************************************************
* 功能描述:二路歸并排序(兩個有序序列)
* 參	數:有序序列下標 f 第一個， s 第二個
* 日	期:2023/11/22                                                   
************************************************************************/
void merge(int arr[], int fBegin, int fEnd, int sBegin, int sEnd, int newArray[])
{int index = fBegin;//新數組的下標int f = fBegin;//遍歷第一個有序序列int s = sBegin;//遍歷第二個有序序列while (f <= fEnd && s <= sEnd){if (arr[f] <= arr[s]){newArray[index++] = arr[f++];}else{newArray[index++] = arr[s++];}}while (f <= fEnd){newArray[index++] = arr[f++];}while (s <= sEnd){newArray[index++] = arr[s++];}memcpy(arr + fBegin, newArray + fBegin, sizeof(int) *(sEnd - fBegin +1));
}//多路歸并排序
void mergeSort(int arr[], int left, int right, int newArray[])
{if (left >= right){return;}int mid = (left + right) / 2;mergeSort(arr, left, mid, newArray);mergeSort(arr, mid + 1, right, newArray);merge(arr, left, mid, mid + 1, right, newArray);
}int main(){int arr[] = {10, 8, 11, 7, 4, 12, 9, 6, 5, 3};int len = sizeof(arr)/sizeof(arr[0]);int newArray[10] = {0};cout << "排序前：";print_array(arr, len);mergeSort(arr, 0, len - 1, newArray);cout << "排序后：";print_array(arr, len);return 0;
}

輸出結果：