題目敘述 Sort an Array
這題就是經典的考排序驗算法，不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。
題目會給定一個輸入陣列，要求我們實作一個排序演算法，把陣列元素從小到大排好。
測試範例
Example 1:Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.
約束條件
Constraints:
1 <= nums.length <= 5 * 10^4
陣列長度介於1~五萬之間。
-5 * 10^4 <= nums[i] <= 5 * 10^4
陣列元素都介於 負五萬 ~ 正五萬 之間。
演算法 採用較佳的O( n logn ) 演算法
題目已經明言規定不可以呼叫程式語言或者平台內建的sort function，就是要求我們真正實作一個upper bound為O( n log n)的排序演算法。
考慮到退化的關係，QuickSort會在最差情況會退到O( n^2 )。
註: 退化的意思就是，Worst case發生在當所有element 都已經排好，或者逆序排好，或者陣列元素都相同的時候。
所以本題我們選擇Merge Sort來實作，Merge sort 即使在最差情況 worst case依然能保障O( n log n)的complexity upper bound 。
程式碼 較佳的O( n logn ) MergeSort演算法
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
# Use divide and conquer strategy with mergesort
def mergeSort(left, right):
if left >= right:
# only one element, no need to sort
# invalid interval, no need to sort
return
# Divide :
mid = left + (right - left) // 2
mergeSort( left , mid )
mergeSort( mid+1, right)
# Conquer, also known as merge
a, b = left, mid+1
merging = []
# Two way merge between left half and right half
while a <= mid and b <= right:
if nums[a] < nums[b]:
merging.append( nums[a] )
a += 1
else:
merging.append( nums[b] )
b += 1
# Only left half remains
while a <= mid:
merging.append( nums[a] )
a += 1
# Only right half remains
while b <= right:
merging.append( nums[b] )
b += 1
# Write back to originally specific interval
nums[left : right+1] = merging
return
複雜度分析
時間複雜度:
O( n log n)，至多 log n 層，每層merge又耗費O(n)去合併左半部和右半部子陣列。
空間複雜度:
O( n ) 合併時耗費O(n)的輔助空間去儲存merge完的結果
Reference:
[1] Python O( n log n) by merge sort — Sort an Array — LeetCode
