排序算法（5）：归并排序

问题

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

归并排序

归并排序采用分治法，将序列分成若干子序列，每个子序列有序后再合并成有序的完整序列。

在数组排序中，如果只有一个数，那么它本身就是有序的。如果有两个数，只需要进行一次比较就可以完成排序。也就是说，数越少，排序越容易。那么，如果有一个由大量数据组成的序列，可以考虑将其不断分解，直到只剩一个数时，本身已经有序，再将这些有序的数组合并在一起，从而完成排序。

图解

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时分解到只剩一个数，不用合并直接返回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)

• 分解：这一步仅仅是计算出子序列的中间位置，需要常数时间 O(1)
• 解决子问题：递归求解两个规模为 n/2 的子问题，所需时间为 2T(n/2)
• 合并：合并算法可以在 O(n) 时间内完成

所以总运行时间为：

当 n>1 时，可以递推求解：

递推最终的规模为 1， 令 2^x = n，则 x = log n，那么