“归并排序”思想虽然很简单，但是对“归并排序”算法的学习，我们可以一窥“分治”和“递归”这两种非常常用的算法思想。
归并排序的思想
归并排序的基本思想是：将两个有序数组归并成一个更大的有序数组。“归并”的过程很简单，请看以下两个有序数组：
有序数组1：。
有序数组2：。
因为数组是有序的，所以每次我们比较每个数组的开头那个元素，谁小，谁拿出来，拿出来的元素的后面的那个元素就成为新的开头元素（我们无须把后面的元素前移一位，只要把定义“开头”的指针后移一位就好了）。所以，我们依次得到 ，这就是“归并”以后的数组。
不难看出，要实现“归并排序”，我们需要与归并之前两个数组元素数目之和的这么多辅助空间。你也很容易想到，只要归并之前，数组是有序的，多来几个有序数组，归并的思路也是一致的：每一次都拿出这些有序数组的第 个元素（索引为
）中最小的。
那么代码如何实现呢？这里就要用到“递归”和“分治”的思想。下面是《算法导论》（第 3 版）中关于“归并排序”介绍部分的伪代码。
可以看到：
1、我们要设计一个能在数组 A 的区间 [p,r] 内完成归并排序功能的函数；
2、每一轮找到 p 和 r 的中点 q，把区间 [p,r] 分成两个子区间，对这两个子区间分别递归调用自己；
3、最后“等待”两个递归调用自己的函数都完成以后，再“mege”一下，这一步就是我们上面提到的“归并排序”的思想。
写到这里，可能还是很模糊，这就是“递归”这件事让人有的时候捉摸不透的原因。我们想想递归到底的情况，即两个数组都只有 个元素的时候，就容易一些了，这时问题就退化为比较两个数的大小的问题了。下面的代码几乎是“模板”，需要在理解的基础上，记忆和练习。
归并排序的实现（第 1 版）
从上面的伪代码中，我们知道，我们要编写一个支持数组指定区间排序的函数，因为这个函数是内部使用的，我们使用 __ 开头：
Python 代码：
def __merge_sort(nums, left, right):
if left >= right:
return
# Python 中整除使用 // 2
# 下面这行代码在 left 和 right 都很大时，left + right 会溢出
mid = (left + right) // 2
__merge_sort(nums, left, mid)
__merge_sort(nums, mid + 1, right)
__merge_of_two_sorted_array(nums, left, mid, right)
def merge_sort(nums):
"""
归并排序的入口函数
:param nums:
:return:
"""
__merge_sort(nums, 0, len(nums) - 1)
说明：1、上面的 __merge_sort 函数就对应了伪代码中的 MERGE-SORT 函数。
2、下面这段代码表示了递归终止条件，即：[left,right] 形成区间时，才调用函数，极端情况下，left==right 时，都不能调用，道理很简单：这个时候，区间只有 个元素，都不能拆成两个数组。
Python 代码：
if left >= right:
return
3、mid = (left + right) // 2 这句代码严格意义上说是错误的，正确的写法是：
Python 代码：
mid = left + (right - left) // 2
因为如果 left 和 right 都很大的话，left + right 可能会溢出（事实上，数组小标要开到一个很大的数也是极少见的），我们将在后面的代码中修正它。
不过还要说的一点是，当 right 很大，left 很小的时候，right - left 也可能越界，只不过这里的 left 和 right 都表示索引， left 不可能是一个绝对值很大的负数。习惯上，我写 mid = left + (right - left) // 2 表明我们注意到可能发生溢出。
下面是合并两个有序数组的代码：
Python 代码：
def __merge_of_two_sorted_array(nums, left, mid, right):
# Python 中切片即复制，复制到一个临时数组中
nums_for_compare = nums[left:right + 1]
i = 0
j = mid - left + 1
# 通过 nums_for_compare 数组中设置两个指针 i、j 分别表示两个有序数组的开始
# 覆盖原始数组
for k in range(left, right + 1):
if i > mid - left:
# i 用完了，就拼命用 j
nums[k] = nums_for_compare[j]
j += 1
elif j > right - left:
# j 用完了，就拼命用 i
nums[k] = nums_for_compare[i]
i += 1
elif nums_for_compare[i] < nums_for_compare[j]:
nums[k] = nums_for_compare[i]
i += 1
else:
assert nums_for_compare[i] >= nums_for_compare[j]
nums[k] = nums_for_compare[j]
j += 1
完整归并排序的代码如下：
Python 代码：
def __merge_of_two_sorted_array(nums, left, mid, right):
# Python 中切片即复制，复制到一个临时数组中
nums_for_compare = nums[left:right + 1]
i = 0
j = mid - left + 1
# 通过 nums_for_compare 数组中设置两个指针 i、j 分别表示两个有序数组的开始
# 覆盖原始数组
for k in range(left, right + 1):
if i > mid - left:
# i 用完了，就拼命用 j
nums[k] = nums_for_compare[j]
j += 1
elif j > right - left:
# j 用完了，就拼命用 i
nums[k] = nums_for_compare[i]
i += 1
elif nums_for_compare[i] < nums_for_compare[j]:
nums[k] = nums_for_compare[i]
i += 1
else:
assert nums_for_compare[i] >= nums_for_compare[j]
nums[k] = nums_for_compare[j]
j += 1
def __merge_sort(nums, left, right):
if left >= right:
return
# 这里有一个陷阱，如果 left 和 right 都很大的话，left + right 容易溢出
# Python 中整除使用 // 2
mid = left + (right - left) // 2
__merge_sort(nums, left, mid)
__merge_sort(nums, mid + 1, right)
__merge_of_two_sorted_array(nums, left, mid, right)
def merge_sort(nums):
"""
归并排序的入口函数
:param nums:
:return:
"""
__merge_sort(nums, 0, len(nums) - 1)
这就是我们实现的第 1 版归并排序。
时间复杂度与空间复杂度
时间复杂度：)
这是我们接触的第 1 个 级别的排序算法，它比前两个
级别快的原因就是，每次我们都一分为二地处理数组，不用在一个很长的数组里进行排序。但它需要辅助的空间来执行“归并”操作，算是一种以“空间”换“时间”的策略吧。
为什么是 呢？因为“归并”的操作呈树形结构。
空间复杂度：)
分析：我们在合并两个有序数组的时候，使用了与两个数组长度之和这么多空间的辅助数组，所以“归并排序”的空间复杂度是 。
这一节的内容就暂时介绍这么多，开始我们慢一点。下一节，我们介绍归并排序的优化。
练习
练习1：LeetCode 第 88 题：合并两个有序数组
传送门：英文网址：88. Merge Sorted Array ，中文网址：88. 合并两个有序数组 。
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
思路1：你当然可以按照我们这一节介绍的合并两个有序数组的方法来完成，因为最后是把 nums1 返回回去，因此，我们要先把 nums1 中的元素拷贝出来，然后再写回 nums1。
Python 代码：
class Solution:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
nums3 = nums1[:]
i = 0
j = 0
for k in range(m + n):
if i == m:
nums1[k] = nums2[j]
j += 1
elif j == n:
nums1[k] = nums3[i]
i += 1
elif nums3[i] < nums2[j]:
nums1[k] = nums3[i]
i += 1
else:
nums1[k] = nums2[j]
j += 1
if __name__ == '__main__':
nums1 = [1, 2, 3, 4, 5, 6, 7, 20, 30, 40, 50]
nums2 = [8, 9, 10, 11, 12, 60, 70, 80]
m = len(nums1)
n = len(nums2)
nums1.extend([None] * n)
s = Solution()
s.merge(nums1, m, nums2, n)
print(nums1)
思路2：考虑到这道题的特殊性，即 nums1 有足够的空间，因此，我们可以从后向前归并，每次从两个数组的末尾选出最大的元素放在 nums1 的末尾，而不使用额外的数组空间。
你可能会担心，nums1 之前有效的元素会不会被覆盖掉，但在这题中，这种情况是不可能出现的。在实现的时候，还是要特别注意一些边界条件。
Python 代码：
class Solution:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
i = m - 1
j = n - 1
for k in range(m + n - 1, -1, -1):
if i == -1:
nums1[k] = nums2[j]
j -= 1
elif j == -1:
nums1[k] = nums1[i]
i -= 1
elif nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
本文源代码
（本节完）
