歸并排序

歸并排序采用分治策略實現穩定排序，其核心思想是將序列遞歸分解后進行有序合并。

def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result

時間復雜度分析

設序列長度為$n$，遞歸樹深度為$\log n$，每層合并操作耗時$O(n)$。遞推公式為：
$$T(n)=2T(\frac{n}{2})+O(n)$$
根據主定理可得時間復雜度為$O(n\log n)$。當處理大規模數據時，這種對數增長特性使算法效率顯著優于$O(n^2)$的簡單排序算法。

該算法的空間復雜度為$O(n)$，主要來源于合并過程中創建的臨時數組。實際應用中可通過原地歸并等優化策略降低空間消耗。