合併排序函式

題目敘述

請提交 sort.h，在其中實作 void merge_sort(int *a, int n)，把長度為 n 的整數陣列 a 由小到大原地排序。排序方式必須是「合併排序」：先把陣列切成左右兩半，各自遞迴排好，再用線性時間把兩段已排序的結果合併起來。

測試程式會讀入陣列、呼叫你的函式，再印出排序後的內容。

輸入格式

• 第 1 行：整數 n。
• 第 2 行：n 個整數。

輸出格式

輸出排序後的陣列，數字之間以一個空格分隔。若 n = 0，輸出一行空行。

限制

• 0 ≤ n ≤ 2 · 10⁵
• 每個數值都在 [−10⁹, 10⁹] 範圍內

範例

範例 1

輸入

5
5 3 5 1 2

輸出

1 2 3 5 5

範例 2

輸入

0

輸出

範例 3

輸入

1
42

輸出

42

範例 4

輸入

7
7 6 5 4 3 2 1

輸出

1 2 3 4 5 6 7

說明

• 範例 1：含有重複數字 5 的小陣列，兩個 5 都要輸出。
• 範例 2：n = 0 時沒有數字，只輸出一行空行。
• 範例 3：只有一個數字，本來就已排序。
• 範例 4：完全反向的陣列。

• 合併時，若左右兩端的數字相等，應先取左半的那一個。
• 合併完的結果要寫回 a，只寫進暫存陣列而不複製回來，a 就不會改變。
• O(n²) 的排序在 n = 2 · 10⁵ 時會超過時限。