Using python show how to time a merge sort such as presented below: def mergeSor

Question

Using python show how to time a merge sort such as presented below:

def mergeSort(list):
if len(list) > 1:
# Merge sort the first half
firstHalf = list[ : len(list) // 2]
mergeSort(firstHalf)

# Merge sort the second half
secondHalf = list[len(list) // 2 : ]
mergeSort(secondHalf)

# Merge firstHalf with secondHalf into list
merge(firstHalf, secondHalf, list)

# Merge two sorted lists */
def merge(list1, list2, temp):
current1 = 0 # Current index in list1
current2 = 0 # Current index in list2
current3 = 0 # Current index in temp

while current1 < len(list1) and current2 < len(list2):
if list1[current1] < list2[current2]:
temp[current3] = list1[current1]
current1 += 1
current3 += 1
else:
temp[current3] = list2[current2]
current2 += 1
current3 += 1

while current1 < len(list1):
temp[current3] = list1[current1]
current1 += 1
current3 += 1

while current2 < len(list2):
temp[current3] = list2[current2]
current2 += 1
current3 += 1

def main():
  
list = [5000, 300000, 250000, 200000, 10000, 150000]
mergeSort(list)
for v in list:
print("Merge sort list: ",str(v) + " ", end = "")
  

main()

Explanation / Answer

Please find my analysis of Merge Sort time complexity:

Assumption: N is a power of two.

For N = 1: time is a constant (denoted by 1)

Otherwise: time to mergesort N elements = time to mergesort N/2 elements plus
time to merge two arrays each N/2 elements.

Time to merge two arrays each N/2 elements is linear, i.e. N

Thus we have:

(1) T(1) = 1

(2) T(N) = 2T(N/2) + N

Next we will solve this recurrence relation. First we divide (2) by N:

(3) T(N) / N = T(N/2) / (N/2) + 1

N is a power of two, so we can write

(4) T(N/2) / (N/2) = T(N/4) / (N/4) +1

(5) T(N/4) / (N/4) = T(N/8) / (N/8) +1
(6) T(N/8) / (N/8) = T(N/16) / (N/16) +1
(7) ……
(8) T(2) / 2 = T(1) / 1 + 1
Now we add equations (3) through (8) : the sum of their left-hand sides
will be equal to the sum of their right-hand sides:

T(N) / N + T(N/2) / (N/2) + T(N/4) / (N/4) + … + T(2)/2 =

T(N/2) / (N/2) + T(N/4) / (N/4) + ….+ T(2) / 2 + T(1) / 1 + LogN

(LogN is the sum of 1s in the right-hand sides)

After crossing the equal term, we get

(9) T(N)/N = T(1)/1 + LogN

T(1) is 1, hence we obtain

(10) T(N) = N + NlogN = O(NlogN)

Hence the complexity of the MergeSort algorithm is O(NlogN).

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.