-
Notifications
You must be signed in to change notification settings - Fork 0
/
MergeSort.py
51 lines (44 loc) · 1.09 KB
/
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
44
45
46
47
48
49
50
import Util;
import time;
import math;
import Sort
class MergeSort():
def __init__(self, intList):
self.intList = intList;
def sort(self, list):
#L = self.intList;
n = len(list)
if n is 1:
return list
mid = math.floor(n/2)
firstHalf = list[0:mid]
secondHalf = list[mid:n]
B = self.sort(firstHalf)
C = self.sort(secondHalf)
self.intList = self.merge(B, C)
return self.intList
def merge(self, B, C):
i = j = 0
A = []
while i < len(B) and j < len(C):
if B[i] <= C[j]:
A.append(B[i])
i += 1
else:
A.append(C[j])
j += 1
if i == (len(B)):
for k in range(j, len(C)):
A.append(C[k])
else:
for k in range(i, len(B)):
A.append(B[k])
return A
L = Util.generateList(10)
def forTime(L):
A = MergeSort(L)
Start = time.time()
M = A.sort(L)
runTime = time.time() - Start
#print(M)
return runTime