整數排序與比較函式溢位

題目敘述

給定 n 個整數，請由小到大（非遞減）排序後輸出。數值之間有可能相距極遠，包含 32 位元整數的最小值與最大值，因此如果你用 qsort 並讓比較函式直接回傳兩數相減的結果，減法本身可能溢位而得到錯誤的排序。比較函式只需要回傳正、零、負三種符號，請用比較運算而不是相減來決定。

輸入格式

• 第 1 行：整數 n，代表陣列長度。
• 第 2 行：n 個整數 a₁, a₂, ..., a_n。若 n = 0，第 2 行為空行。

輸出格式

輸出一行，為排序後的 n 個整數，以空格分隔。若 n = 0，輸出一個空行。

限制

• 0 ≤ n ≤ 1000
• 每個陣列元素在 [−10⁹, 10⁹] 範圍內
• 數值可能包含 INT_MIN 與 INT_MAX

範例

範例 1

輸入

5
5 3 5 1 2

輸出

1 2 3 5 5

有一個重複的值（5 出現兩次），兩個 5 都要印出。

範例 2

輸入

0

輸出

沒有任何元素時，輸出一個空行，不是 0，也不能完全不輸出。

範例 3

輸入

1
-5

輸出

-5

只有一個元素時原樣輸出即可。

範例 4

輸入

9
2147483647 -2147483648 0 -2147483648 2147483647 1 -1 2147483646 -2147483647

輸出

-2147483648 -2147483648 -2147483647 -1 0 1 2147483646 2147483647 2147483647

兩端的極值各出現兩次。若比較函式直接用相減，INT_MAX - INT_MIN 會溢位，排序結果就會錯。

範例 5

輸入

1
42

輸出

42

只有一個元素 42，原樣輸出。

說明

• 比較函式可以寫成 (a > b) − (a < b)，結果只會是 −1、0 或 1，不會溢位。
• 只用小數值測試時，相減的寫法看起來完全正常，所以請特別用極端值檢查自己的程式。