Runtime comparison between merge sort, insertion sort and recursive insertion sort in python

user_8454838 0
Viewed 95
def merge_sort(unorderedList):
    if len(unorderedList) > 1:
        mid = len(unorderedList) // 2 
        left = unorderedList[:mid]
        right = unorderedList[mid:]
        merge_sort(left)
        merge_sort(right)
        i = 0
        j = 0
        k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                unorderedList[k] = left[i]
                i += 1
            else:
                unorderedList[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            unorderedList[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            unorderedList[k] = right[j]
            j += 1
            k += 1

def insertion_sort(list1):
    for i in range(1, len(list1)):
        key = list1[i]
        j = i - 1 
        while j >= 0 and list1[j] > key:
            list1[j + 1] = list1[j]
            j -= 1
        list1[j + 1] = key

def recursive_insertion_sort(arr, n):
    if n <= 1:
        return

    recursive_insertion_sort(arr, n-1)
    last = arr[n-1]
    j = n-2
     
    while j >= 0 and arr[j] > last:
        arr[j + 1] = arr[j]
        j -= 1
 
    arr[j + 1] = last

import time
import random
t0 = time.time()
insertion_sort([random.randint(-10000, 10000) for i in range(50000)])
t1 = time.time()
recursive_insertion_sort([random.randint(-10000, 10000) for i in range(50000)])
t2 = time.time()
merge_sort([random.randint(-10000, 10000) for i in range(50000)])
t3 = time.time()

print("insertion sort timer : ", t1 - t0)
print("recursive insertion sort timer : ", t2 - t1)
print("merge sort timer : ", t3 - t2)

I used these three functions to compare their runtimes on a 50 thousand membered random list
And i got these times with python 3.10 in vscode

insertion sort timer : 78.13s
recursive insertion sort timer : 0.068s
merge sort timer : 0.209s
Is this correct? And if so, can you explain it please?
Considering merge sort has an order of O(nlogn) and insertion sorts order is O(n^2), how is this happening?

EDIT: added the code and method used for time testing.

time-complexity sorting python
1 Answers

Since these functions are performing an "inplace" sort, I suspect that your metrics were not starting from the same original list.

For example, if you test merge_sort first on list A and then test insertion_sort on A, that second sort gets an already sorted list which that algorithm should benefit from. This is likely what happened between the "insertion sort" measurement and the "recursive insertion sort" measurement.

Theoretically, recursive_insertion_sort function shouldn't be able to sort any list with more than 990 items. So, I'm guessing you changed the maximum recursion depth limit (if you didn't then something else is wrong in the experiment)

If you test each sort independently (or on copies of the original list), you should get very different results.

user_52375600
Related