1 #!/usr/bin/env python
2 # -*- coding:utf-8 -*-
3
4 def Mege(list):
5 if(len(list)<=1):
6 return list
7 num = int(len(list)/2)
8 left = Mege(list[:num])
9 right = Mege(list[num:])
10 return Mag(left,right)
11
12 def Mag(left,right):
13 l,r=0,0
14 result = []
15 while l<len(left) and r<len(right):
16 if left[l]<right[r]:
17 result.append(left[l])
18 l += 1
19 else:
20 result.append(right[r])
21 r += 1
22 result += left[l:]
23 result += right[r:]
24 return result
25
26 if __name__ == '__main__':
27 print(Mege([1,2,3,11,90,13,20,58,77,28,10]))