Feb-24-2020, 10:59 PM
(This post was last modified: Feb-24-2020, 10:59 PM by gregpederseng.)
I am trying to determine time complexity of the MergeSort algorithm below:
def sortedMerge(self, a, b):
result = None
if a == None:
return b
if b == None:
return a
if a.data <= b.data:
result = a
result.next = self.sortedMerge(a.next, b)
else:
result = b
result.next = self.sortedMerge(a, b.next)
return result
def mergeSort(self, h):
import time
start = time.time()
if h == None or h.next == None:
return h
middle = self.getMiddle(h)
nexttomiddle = middle.next
middle.next = None
left = self.mergeSort(h)
right = self.mergeSort(nexttomiddle)
sortedlist = self.sortedMerge(left, right)
end = time.time()
total = (end - start) * 1000.0
return sortedlist, total
def getMiddle(self, h):
if (h == None):
return h
slow = h
fast = h
while (fast.next != None and
fast.next.next != None):
slow = slow.next
fast = fast.next.next
return slow
#Driver Code
y = mergeSort(array.head)
print(y)The problem arises when I try to calculate runtime, and try to return the runtime (total) with sortedlist in the mergeSort function. When I do, I get error "tuple object has no attribute data".