Medium
912. Sort an Array
arraydivide-and-conquersortingheap-priority-queuemerge-sortbucket-sortradix-sortcounting-sort
解題說明
Sort an Array
題目描述：
給定一個整數陣列 nums，將其按升序排列後返回。要求不使用內建排序函數，且時間複雜度為 O(n log n)。
解題思路： **合併排序（Merge Sort）**是最穩定的 O(n log n) 演算法，不受輸入分佈影響：
- 分割：將陣列從中間切成左右兩半。
- 遞迴排序：分別對左右兩半遞迴排序。
- 合併：使用雙指標將兩個已排序的子陣列合併成一個有序陣列。
合併排序是穩定排序，最差情況也是 O(n log n)，非常適合本題。
注意：快速排序雖然平均 O(n log n)，但最差 O(n^2)，在 LeetCode 的某些測試案例中會 TLE（尤其是已排序或大量重複元素的情況），除非使用隨機 pivot 或三路劃分。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 遞迴深度 log n，每層合併操作為 O(n)。
空間複雜度：O(n) — 合併時需要輔助陣列，加上遞迴棧深度 O(log n)。
虛擬碼
1. mergeSort(nums, left, right): a. If left >= right, return. b. mid = (left + right) / 2. c. mergeSort(nums, left, mid). d. mergeSort(nums, mid + 1, right). e. merge(nums, left, mid, right). 2. merge(nums, left, mid, right): a. Create temporary array. b. Use two pointers i = left, j = mid + 1. c. Compare and copy smaller element to temp. d. Copy remaining elements. e. Copy temp back to nums[left..right].
其他解法
隨機化快速排序 + 三路劃分：O(n log n) 平均時間、O(log n) 空間。隨機選 pivot 避免最差情況，三路劃分（Dutch National Flag）高效處理大量重複元素。但最差情況仍為 O(n^2)。
堆排序：O(n log n) 時間、O(1) 空間。原地排序且最差情況有保證，但實際常數較大且不穩定。
基數排序：O(n * d) 時間、O(n) 空間，其中 d 為數字位數。需要處理負數（偏移），適用於值域有限的整數排序。
延伸思考
- 快速排序在哪些輸入模式下會退化到 O(n^2)？隨機化 pivot 如何解決？
- 合併排序是穩定的，而堆排序不穩定。在什麼應用場景下穩定性很重要？
- 如何實現原地合併排序（In-place Merge Sort），使空間複雜度降到 O(log n)？