Question

Runtime complexity of Insertion sort and Mergesort algirthms- and analysis with different size of inputs: In python

Implement a method to sort a given array using the merge sort algorithm.

Write a driver program to test the merge sort algorithm and insertion sort algorithm for the arrays of varying lengths provided.. Ex: array lenth 100, Array lenth 1000 etc.

Compare the execution time of merge sort with insertion sort. Make sure you use the same array to compare the performance. Use a table or plot to summarize the results and document your observations and analysis in the report.

Based on the performance results obtained above, modify the merge sort algorithm such that when the array size gets small enough, you would invoke insertion sort instead of invoking merge sort (hint: you have to change the base condition in the recursion). Instead of hardcoding the array size make it a variable that you can pass as an argument to the merge sort method and test this cutoff value with at least four different values.

Test the program for the same array sizes and values. Compare the performance with the original merge sort implementation, plot the execution times, and document the analysis in your lab report.

Answer 1

import random
MAX_INT = 100
MIN_INT = 0
import time

def insertionSort(x) :
    result = []
    for i in range( 1, len(x)):
        result.append(x[i]);

    for i in range( 1, len(result)):
        temp = result[i]
        k = i
        while k > 0 and temp < result[k-1] :
            result[k] = result[k - 1]
            k -= 1
        result[k] = temp
    return result

def mergeSort(x) :
    if len(x) <= 1:
        return x
    mid = int(len(x)/2)
    a = mergeSort(x[:mid])
    b = mergeSort(x[mid:])
    return merge(a,b)

def mergeSortWithInsertion(x, minSize) :
    if len(x) <= minSize or len(x) <= 1 :
        return insertionSort(x)
    mid = int(len(x)/2)
    a = mergeSortWithInsertion(x[:mid], minSize)
    b = mergeSortWithInsertion(x[mid:], minSize)
    return merge(a,b)

def merge(a, b) :
    result = []
    i = 0
    j = 0
    while i<len(a) and j<len(b) :
        if a[i] > b[j] :
            result.append(b[j])
            j += 1
        else :
            result.append(a[i])
            i += 1
    result += a[i:]
    result += b[j:]
    return result

def getRandArrayOfRandSize(n) :
    listOfNumbers = [];
    for x in range (0, n):
        listOfNumbers.append(random.randint(MIN_INT, MAX_INT))
    return listOfNumbers

## Testing Code
for i in range(1,11) :
    x = getRandArrayOfRandSize(i*2000)

    print("\n------ STARTING CASE-", i , "------ [ Input Size = ", len(x), "]")
    start_time = time.clock()
    insertionSort(x)
    print("insertion sort = ", time.clock() - start_time, "seconds")

    start_time = time.clock()
    mergeSort(x)
    print("merge sort = ", time.clock() - start_time, "seconds")

    start_time = time.clock()
    mergeSortWithInsertion(x, 10)
    print("merge sort + insertion_sort (size = 10) = ", time.clock() - start_time, "seconds")

    start_time = time.clock()
    mergeSortWithInsertion(x, 25)
    print("merge sort + insertion_sort (size = 25) = ", time.clock() - start_time, "seconds")

    start_time = time.clock()
    mergeSortWithInsertion(x, 50)
    print("merge sort + insertion_sort (size = 50) = ", time.clock() - start_time, "seconds")

    start_time = time.clock()
    mergeSortWithInsertion(x, 100)
    print("merge sort + insertion_sort (size = 100) = ", time.clock() - start_time, "seconds")

    start_time = time.clock()
    mergeSortWithInsertion(x, 250)
    print("merge sort + insertion_sort (size = 250) = ", time.clock() - start_time, "seconds")

    start_time = time.clock()
    mergeSortWithInsertion(x, 500)
    print("merge sort + insertion_sort (size = 500) = ", time.clock() - start_time, "seconds")

    print("------ END OF CASE-" , i , "------ \n")

OUTPUT

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

------ STARTING CASE- 1 ------ [ Input Size = 2000 ]
insertion sort = 0.097832 seconds
merge sort = 0.005801 seconds
merge sort + insertion_sort (size = 10) = 0.003716 seconds
merge sort + insertion_sort (size = 25) = 0.004153 seconds
merge sort + insertion_sort (size = 50) = 0.004135 seconds
merge sort + insertion_sort (size = 100) = 0.005187 seconds
merge sort + insertion_sort (size = 250) = 0.013626 seconds
merge sort + insertion_sort (size = 500) = 0.025309 seconds
------ END OF CASE- 1 ------

------ STARTING CASE- 2 ------ [ Input Size = 4000 ]
insertion sort = 0.388726 seconds
merge sort = 0.011991 seconds
merge sort + insertion_sort (size = 10) = 0.008189 seconds
merge sort + insertion_sort (size = 25) = 0.008449 seconds
merge sort + insertion_sort (size = 50) = 0.0093 seconds
merge sort + insertion_sort (size = 100) = 0.011117 seconds
merge sort + insertion_sort (size = 250) = 0.027705 seconds
merge sort + insertion_sort (size = 500) = 0.050494 seconds
------ END OF CASE- 2 ------

------ STARTING CASE- 3 ------ [ Input Size = 6000 ]
insertion sort = 0.86935 seconds
merge sort = 0.018749 seconds
merge sort + insertion_sort (size = 10) = 0.013192 seconds
merge sort + insertion_sort (size = 25) = 0.013598 seconds
merge sort + insertion_sort (size = 50) = 0.016025 seconds
merge sort + insertion_sort (size = 100) = 0.021048 seconds
merge sort + insertion_sort (size = 250) = 0.033279 seconds
merge sort + insertion_sort (size = 500) = 0.059811 seconds
------ END OF CASE- 3 ------

------ STARTING CASE- 4 ------ [ Input Size = 8000 ]
insertion sort = 1.566274 seconds
merge sort = 0.025594 seconds
merge sort + insertion_sort (size = 10) = 0.017992 seconds
merge sort + insertion_sort (size = 25) = 0.018349 seconds
merge sort + insertion_sort (size = 50) = 0.019576 seconds
merge sort + insertion_sort (size = 100) = 0.024405 seconds
merge sort + insertion_sort (size = 250) = 0.055694 seconds
merge sort + insertion_sort (size = 500) = 0.102565 seconds
------ END OF CASE- 4 ------

------ STARTING CASE- 5 ------ [ Input Size = 10000 ]
insertion sort = 2.421797 seconds
merge sort = 0.033471 seconds
merge sort + insertion_sort (size = 10) = 0.022663 seconds
merge sort + insertion_sort (size = 25) = 0.024298 seconds
merge sort + insertion_sort (size = 50) = 0.026851 seconds
merge sort + insertion_sort (size = 100) = 0.034553 seconds
merge sort + insertion_sort (size = 250) = 0.050001 seconds
merge sort + insertion_sort (size = 500) = 0.08531 seconds
------ END OF CASE- 5 ------

------ STARTING CASE- 6 ------ [ Input Size = 12000 ]
insertion sort = 3.487232 seconds
merge sort = 0.041774 seconds
merge sort + insertion_sort (size = 10) = 0.028485 seconds
merge sort + insertion_sort (size = 25) = 0.030319 seconds
merge sort + insertion_sort (size = 50) = 0.035072 seconds
merge sort + insertion_sort (size = 100) = 0.045909 seconds
merge sort + insertion_sort (size = 250) = 0.069218 seconds
merge sort + insertion_sort (size = 500) = 0.12175 seconds
------ END OF CASE- 6 ------

------ STARTING CASE- 7 ------ [ Input Size = 14000 ]
insertion sort = 4.75054 seconds
merge sort = 0.04913 seconds
merge sort + insertion_sort (size = 10) = 0.033935 seconds
merge sort + insertion_sort (size = 25) = 0.034279 seconds
merge sort + insertion_sort (size = 50) = 0.037331 seconds
merge sort + insertion_sort (size = 100) = 0.042495 seconds
merge sort + insertion_sort (size = 250) = 0.091504 seconds
merge sort + insertion_sort (size = 500) = 0.162114 seconds
------ END OF CASE- 7 ------

------ STARTING CASE- 8 ------ [ Input Size = 16000 ]
insertion sort = 6.213865 seconds
merge sort = 0.055599 seconds
merge sort + insertion_sort (size = 10) = 0.039368 seconds
merge sort + insertion_sort (size = 25) = 0.040357 seconds
merge sort + insertion_sort (size = 50) = 0.043254 seconds
merge sort + insertion_sort (size = 100) = 0.051887 seconds
merge sort + insertion_sort (size = 250) = 0.115063 seconds
merge sort + insertion_sort (size = 500) = 0.209497 seconds
------ END OF CASE- 8 ------

------ STARTING CASE- 9 ------ [ Input Size = 18000 ]
insertion sort = 8.240016 seconds
merge sort = 0.06545 seconds
merge sort + insertion_sort (size = 10) = 0.045546 seconds
merge sort + insertion_sort (size = 25) = 0.046864 seconds
merge sort + insertion_sort (size = 50) = 0.050393 seconds
merge sort + insertion_sort (size = 100) = 0.061606 seconds
merge sort + insertion_sort (size = 250) = 0.08762 seconds
merge sort + insertion_sort (size = 500) = 0.14387 seconds
------ END OF CASE- 9 ------

------ STARTING CASE- 10 ------ [ Input Size = 20000 ]
insertion sort = 9.641744 seconds
merge sort = 0.07346 seconds
merge sort + insertion_sort (size = 10) = 0.053326 seconds
merge sort + insertion_sort (size = 25) = 0.053757 seconds
merge sort + insertion_sort (size = 50) = 0.057143 seconds
merge sort + insertion_sort (size = 100) = 0.071182 seconds
merge sort + insertion_sort (size = 250) = 0.103872 seconds
merge sort + insertion_sort (size = 500) = 0.17565 seconds
------ END OF CASE- 10 ------