Question

Python Merge Sort

Adjust the following code so that you can create random lists of numbers of lengths 10, 15, and 20.

You will run the merge sort 10 times for each length. Record the run time for the length and then calculate the average time to sort.

Finally, compare the average run time for each length to the average time for the Merge Sort.

--------------------------------------------

Initial python code:

import random
import time

def mergeSort(alist):
print("Splitting ",alist)
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]

mergeSort(lefthalf)
mergeSort(righthalf)

i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1

while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1

while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

import random mport tlme def mergeSort(alist) print"Splitting ",alist) if len(alist)>l: mid- len(alist)//2 lefthalf - alist:mid] righthalf - alist[mid: ] mergeSort(lefthalf) mergeSort( righthalf) i-0 While flefthal lefthal fighthajelen(righthalf) alist[kJ-leftha I f[i] i-i+1 else: alist[k]-righthalftj] j-j+1 k-k+1 while i < len(lefthalf): alist[k]-lefthalf[i] k-k+1 while j < len( righthalf) alist[k]-righthalftj] print "Merging ",alist) alist- [54,26,93,17,77,31,44,55,20] mergeSort(alist) print(alist)

Answer 1

Hello, I have something to point out. The lengths 10, 15 or 20 is too low to calculate the run time for this merge sort. The results will always display 0 since the time required to sort lists of these lengths is very minute. To see any notable changes in time, we should use these values multiplied by 100 atleast. So in this program, I have used the lengths 1000, 1500 and 2000 instead of 10,15 and 20. You can change these values as you like, just modify the list called ‘lengths’ as you needed.

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

#code

import random
import time

def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

#defining a list of lengths
lengths=[1000,1500,2000]
#an empty list to store average run times
avg_run_times=[]
#a variable to store total run time
total_run_time=0
#looping through each index in lengths list
for i in range(len(lengths)):
    temp=0 #total run time for current length
    #looping for 10 times
    for k in range(10):
        #creating a random list containing lengths[i] number of elements
        aList=[random.randint(0,1000) for j in range(lengths[i])]
        # recording start time
        start = time.time()
        #sorting
        mergeSort(aList)
        #recording end time
        end = time.time()
        #finding elapsed time in seconds
        elapsed_time = end - start
        #adding to temp
        temp+=elapsed_time
    #finding average run time for current length
    avg= temp/10
    #adding to avg_run_times
    avg_run_times.append(avg)
    #adding temp to total_run_time
  total_run_time+=temp
   
#finding average time for performing sorting of all lengths
avg_time=total_run_time/(len(lengths)*10)
#displaying heading
print('{:<15s} {:<15s} {:<15s} {:<15s}'.format('Length','Average Time', 'Final Average','Difference'))
#looping and printing length, average time, final average (average taken for all lengths),
#and the difference between average of current length and average as a whole
for i in range(len(lengths)):
    print('{:<15d} {:<15.2f} {:<15.2f} {:<15.2f}'.format(lengths[i], avg_run_times[i], avg_time, avg_run_times[i]-avg_time))

#output

Length 1000 1500 2000 Final Average Difference 0.02 0.02 0.02 Average Time 0.01 0.02 0.03 0.01 0.00 0.01