1 def partition(nums, left, right):
 2     if left >= right:
 3         return 
 4     mid = left + (right - left)//2
 5     pivot = nums[mid]
 6     nums[mid], nums[left] = nums[left], nums[mid]
 7     j = left
 8     for i in range(left+1, right+1):
 9         if nums[i] < pivot:
10             j += 1 #比pivot小的都放在left+1到j，最后left和j交换位置，就能得到left到j-1都比pivot小
11             nums[j], nums[i] = nums[i], nums[j]
12     nums[left], nums[j] = nums[j], nums[left]
13     partition(nums, left, j - 1)
14     partition(nums, j + 1, right)
15     return nums

 1 def MergeSort(lists):
 2     if len(lists) <= 1:
 3         return lists
 4     num = len(lists) // 2
 5     left = MergeSort(lists[:num])                   
 6     right = MergeSort(lists[num:])
 7     return Merge(left, right)
 8 
 9 def Merge(left, right):
10     l, r = 0, 0
11     result = []
12     while l < len(left) and r < len(right):
13         if left[l] <= right[r]:
14             result.append(left[l])
15             l += 1
16         else:
17             result.append(right[r])
18             r += 1
19     result += list(left[l:])
20     result += list(right[r:])
21     return result