归并排序

归并排序 (Merge Sort)

• 时间复杂的$O(NlogN)$，空间复杂度$O(N)$

Note

归并排序是一种递归行为，因此使用 Master 公式 计算归并排序的时间复杂度

思路

利用二分法的思想，二分之后把两边排好序，先左边排序，再右边排序，在合并，复制到一个新的数组中（具体来说，在Merge的时候，可以开辟一个临时空间，左右侧指针从两区间左侧开始，哪个小拷贝哪个到临时变量中，之后移动指针，直到其中一个越界，然后直接拷贝另一个剩下的。）利用递归重复上述步骤

也可以说，让其整体有序的过程用了外排序，即借助外部数组（就那个临时变量）排好序。

实际代码

这里给出两个版本，一个我自己实现的版本，一个是网友的版本，相比来说，网友的版本更加适合python。

我实现的版本

该版本中，主要注意指针的length的关系，因为正确的索引是从 0~N-1，而长度为N，当初我在这里卡了好久好久。

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]: 
        ''' Merge Sort '''
        if len(nums) == 0:
            return nums
 
        self.nums = nums
        mergeRes = self.mergeSort(pstart=0, pend=len(nums)-1)
        return mergeRes
 
    def mergeSort(self, pstart, pend): # 不含pend的边界
        if pend == pstart:
            return [self.nums[pstart]]
        else:
            pmid = (pend + pstart) // 2
            # 如果下面两个递归有重复的部分，比如都含有mid边界，一定会爆掉。
            leftRes = self.mergeSort(pstart, pmid)
            rightRes = self.mergeSort(pmid+1, pend)
            mergeRes = self.merge(leftRes, rightRes)
            return mergeRes
 
    def merge(self, leftRes, rightRes):
        left = 0
        right = 0
        mergeRes = []
        while( (left < len(leftRes)) and (right < len(rightRes))):
            if leftRes[left] < rightRes[right]:
                mergeRes.append(leftRes[left])
                left += 1
            else:
                mergeRes.append(rightRes[right])
                right += 1
 
        if left == len(leftRes):
            mergeRes.extend(rightRes[right:])
        if right == len(rightRes):
            mergeRes.extend(leftRes[left:])
 
        return mergeRes

网友版本

该版本没有采用指针的方式，而是直接传入了输入。我的版本还新建了 self.nums ，不够理想

class Solution: 
	def sortArray(self, nums: List[int]) -> List[int]: 
		''' Merge Sort ''' 
		mergeRes = self.mergeSort(nums) 
		return mergeRes 
		
	def mergeSort(self, nums): 
		if len(nums) <= 1: 
			return nums # 退出递归的条件
		else: 
			mid = len(nums)//2 
			leftRes = self.mergeSort(nums[:mid]) 
			rigthRes = self.mergeSort(nums[mid:]) 
			mergeRes = self.merge(leftRes, rigthRes) 
			return mergeRes 
		
	def merge(self, leftRes, rightRes): 
		left = 0 
		right = 0 
		mergeRes = [] 
		while(left < len(leftRes) and right < len(rightRes)): 
			if leftRes[left] < rightRes[right]: 
				mergeRes.append(leftRes[left]) 
				left += 1 
			else: 
				mergeRes.append(rightRes[right]) 
				right += 1 
				
		if left == len(leftRes): 
			mergeRes.extend(rightRes[right:]) 
			
		if right == len(rightRes): 
			mergeRes.extend(leftRes[left:]) 
 
		# 也能直接这样，利用了List的加法操作，等价于 .extend(newList)
		# mergeRes += rightRes[right:]
		# mergeRes += leftRes[left:]
		return mergeRes

为什么该算法可以达到 $O(NlogN)$ 的时间复杂度？

$O(N^2)$ 的那些算法中浪费了大量的比较行为，它们每一轮的比较行为都是独立，每一轮的比较只决定一个数字的位置。而归并排序并没有浪费比较行为，它把每一轮的比较得到的信息变成一个有序部分，使得后面的比较能够利用上这个信息，因此能够达到 $O(NlogN)$。