Algorithms-and-Data-Structures/python/sorting/mergesort.py at master · sreejeet/Algorithms-and-Data-Structures · 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
45
46
47
48
49
50
51
52
import time

def mergesorted(a):
	if len(a) <= 1:
		return a

	mid = len(a)//2
	L = mergesorted(a[:mid])
	R = mergesorted(a[mid:])
	a = []
	x = y = 0

	while True:
		Lx = L[x] if x < len(L) else None
		Ry = R[y] if y < len(R) else None
		if Lx == None and Ry == None:
			break
		if Lx == None:
			a.extend(R[y:])
			break
		if Ry == None:
			a.extend(L[x:])
			break
		if len(Lx) < len(Ry):
			a.append(Lx)
			x+=1
		else:
			a.append(Ry)
			y+=1

	return a

if __name__ == '__main__':
	a = [
		"#####",
		"######",
		"#",
		"#########",
		"##########",
		"########",
		"####",
		"###",
		"#######",
		"##",
	]

	print(mergesorted(a))


""" Output
['#', '##', '###', '####', '#####', '######', '#######', '########', '#########', '##########']
"""