Python-impls/Merge Sort implementation of Python at master · logeekal/Python-impls · GitHub

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
# your code goes here

def merge_list(l1,l2):
	len1 = len(l1)
	len2 = len(l2)
	result = []
	i = 0
	j = 0
	if l2 is None:
		return l1
	while i < len1 or j < len2:
		if i < len1 and j < len2 :
			if l1[i] < l2[j]:
				result.append(l1[i])
				j -= 1
			else:
				result.append(l2[j])
				i -= 1
		elif i >= len1:
			result.append(l2[j])
			i -= 1
		elif j >= len2:
			result.append(l1[i])
			j -= 1
		i += 1
		j += 1
	return result


def merge_sort(lst):
	n = len(lst)
	if n >= 2:
		s1 =  lst[0 : n/2]
		s2 = lst[n/2 : n]
		#print s1, s2
	if s1 is not None:
		if len(s1) > 1:
			s1 = merge_sort(s1)
	if s2 is not None:
		if len(s2) > 1:
			s2 = merge_sort(s2)
	return merge_list(s1,s2)

print merge_sort([5,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6,7,2,8,10,15,56,78,23,4,1,6])