def merge_sort(arr):
if len(arr) == 1:
return arr
p = 0
n = len(arr)
q = (p+n)//2
return merge(arr, merge_sort(arr[p:q]), merge_sort(arr[q:]))
def merge(arr, arr1, arr2):
temp = list()
i = j = 0
for r in range(len(arr)):
if i < len(arr1) and j < len(arr2):
# <= 保证稳定性
if arr1[i] <= arr2[j]:
temp.append(arr1[i])
i += 1
else:
temp.append(arr2[j])
j += 1
else:
if i < len(arr1):
temp.extend(arr1[i:])
else:
temp.extend(arr2[j:])
return temp
def quick_sort(arr):
if len(arr) <= 1:
return arr
privot = arr[0]
larr, rarr = partition(arr[1:], privot)
return quick_sort(larr) + [privot] + quick_sort(rarr)
def partition(arr, privot):
i = 0
for j in range(len(arr)):
if arr[j] < privot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
j += 1
return arr[:i], arr[i:]
