1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
def recursion(nums,l,r):
if l==r:
print([nums[l]])
return [nums[l]]
mid = (l+r)>>1
left = recursion(nums,l,mid)
right = recursion(nums,mid+1,r)
print(left,right)
print(merge(left,right))
return merge(left,right)
def merge(left,right):
l_n =len(left)
r_n =len(right)
i = j = 0
ans = []
while i<l_n and j<r_n :
if left[i] <= right[j]:
ans.append(left[i])
i += 1
if i == l_n:
ans += right[j:]
break
if left[i] > right[j]:
ans.append(right[j])
j += 1
if j==r_n:
ans += left[i:]
break
return ans
def k_road_MergeSort(nums,l,r):
if nums==None or len(nums)==1:
return nums
return recursion(nums,l,r)
if __name__ == '__main__':
list_ = [7,4,2,1,5,6,9,0]
list_ = k_road_MergeSort(list_,0,len(list_)-1)
print(list_)
|