主題
題目連結：
題目意譯：
給定一非遞減排序之整數陣列 nums ，回傳非遞減之排序陣列，其元素為 nums 之元素之平方。
限制：
1 ≦ nums.length ≦ 10 ^ 4
-10 ^ 4 ≦ nums[i] ≦ 10 ^ 4
nums 按照非遞減之順序排序。
進階： 將每個元素平方後再排序新的陣列是非常直觀的，那你可以找到一個 O(n) 的解法嗎？
範例測資：
範例 1：
輸入： nums = [-4,-1,0,3,10]
輸出： [0,1,9,16,100]
解釋： 平方後，陣列變為 [16,1,0,9,100]。排序後，變為 [0,1,9,16,100]。
範例 2：
輸入： nums = [-7,-3,2,3,11]
輸出： [4,9,9,49,121]
解題思維：
先找到第一個 ≧ 0 的數字（如果有的話），將原陣列分為非負整數部分以及負整數部分（這部分請反轉）。例如 [-4,-1,0,3,10] 會變為 [0,3,10] 以及 [-1,-4]。
將兩者分開後，可以發現兩者元素平方（接續上例）：
[0,9,100]
[1,16]
兩者各自恰好為已按照非遞減之順序所排序。
因此接著我們可以按照合併排序（Merge Sort）之精神（因為沒有直接講解過合併排序，但是有類似的，如這題），將兩子陣列合併即得到所求陣列。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
