問題

排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]

歸并排序

歸并排序采用分治法，將序列分成若干子序列，每個子序列有序后再合并成有序的完整序列。

在數(shù)組排序中，如果只有一個數(shù)，那么它本身就是有序的。如果有兩個數(shù)，只需要進行一次比較就可以完成排序。也就是說，數(shù)越少，排序越容易。那么，如果有一個由大量數(shù)據(jù)組成的序列，可以考慮將其不斷分解，直到只剩一個數(shù)時，本身已經(jīng)有序，再將這些有序的數(shù)組合并在一起，從而完成排序。

圖解

1. 將待排序元素分成大小大致相同的兩個序列
2. 對兩個序列分別進行歸并排序
3. 將排好序的有序子序列進行合并，得到最終的有序序列
   

代碼

# 合并, 將兩個有序的子序列合并成一個序列
def merge(nums, low, mid, high):i, j = low, mid + 1k = 0temp = [0] * (high - low + 1)while i <= mid and j <= high:if nums[i] <= nums[j]:temp[k] = nums[i]i += 1else:temp[k] = nums[j]j += 1k += 1if i <= mid:temp[k:] = nums[i:mid+1]if j <= high:temp[k:] = nums[j:high+1]nums[low:high+1] = tempreturn numsdef merge_sort(nums, low = 0, high = len(nums)-1):if low < high:					# low = high時分解到只剩一個數(shù)，不用合并直接返回mid = low + (high - low) // 2merge_sort(nums, low, mid)			# 對左半部分進行歸并排序merge_sort(nums, mid+1, high)		# 對右半部分進行歸并排序return merge(nums, low, mid, high)	# 合并為有序子序列else:return nums

時間復雜度

歸并算法的時間復雜度為 O(nlogn)

• 分解：這一步僅僅是計算出子序列的中間位置，需要常數(shù)時間 O(1)
• 解決子問題：遞歸求解兩個規(guī)模為 n/2 的子問題，所需時間為 2T(n/2)
• 合并：合并算法可以在 O(n) 時間內完成

所以總運行時間為：

當 n>1 時，可以遞推求解：

遞推最終的規(guī)模為 1， 令 2^x = n，則 x = log n，那么