-
Notifications
You must be signed in to change notification settings - Fork 126
/
MergeSort.py
43 lines (35 loc) · 918 Bytes
/
MergeSort.py
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
import random
def MergeSort(A, p, r):
q = (p + r) / 2 # Find the middle
if p < r:
MergeSort(A, p, q) # MergeSort A[p...q]
MergeSort(A, q + 1, r) # MergeSort A[p+1....r]
return Merge(A, p, q, r)
# The guard in Merge()
MAX = 10000
def Merge(A, p, q, r):
L = []
R = []
for i in range(p, q + 1): # Copy the left side.
L.append(A[i])
for i in range(q + 1, r + 1): # Copy the right side.
R.append(A[i])
L.append(MAX) # Add guard to the end.
R.append(MAX) # Add guard to the end.
i = 0
j = 0
for k in range(p, r + 1):
if L[i] < R[j]:
A[k] = L[i]
i = i + 1
else:
A[k] = R[j]
j = j + 1
return A
print "Now displaying MergeSort"
A = []
s = random.randint(5, 100)
for i in range(0, s):
A.append(random.randint(0, 1000))
print A
print MergeSort(A, 0, len(A) - 1)