递归实现方式
def merge(l, m, r):
L = arr[l:m+1]
R = arr[m+1: r+1]
i, j, k = 0, 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
arr[l+k] = L[i]
i += 1
else:
arr[l+k] = R[j]
j += 1
k += 1
if i < len(L):
arr[l+k:r+1] = L[i:]
elif j < len(R):
arr[l+k:r+1] = R[j:]
def mergesort(arr, l, r):
if l < r :
m = (l + r) // 2
print("l,m,r", l,m,r)
mergesort(arr, l, m)
mergesort(arr, m+1, r)
merge(l, m, r)
arr = [12, 11, 13, 5, 6, 7,88]
mergesort(arr, 0, len(arr)-1)
print(arr)
循环实现方式
def merge(arr, l, m, r):
L = arr[l:m+1]
R = arr[m+1: r+1]
i, j, k = 0, 0, 0
while i < len(L) and j < len(R):
if L[i] <= R[j]:
arr[l+k] = L[i]
i += 1
else:
arr[l+k] = R[j]
j += 1
k += 1
if i < len(L):
arr[l+k:r+1] = L[i:]
elif j < len(R):
arr[l+k:r+1] = R[j:]
def mergelayer(arr,k):
i = 0
while i+2*k < len(arr):
merge(arr, i, i+k-1, i+2*k-1)
i += 2*k
if len(arr)-i > k:
merge(arr, i, i+k-1, len(arr)-1)
def mergesort(arr):
k = 1
while k
