Binary Insertion Sort vs. Quicksort

I was looking at different sorting algorithms and their performance (link) and then I tried to implement some sorting algorithms myself. I wanted to improve them as well and so, as I was coding the insertion sort, I thought why not to use binary search, as the first part of array is already sorted, and in order to get rid of swaps, use an additional array. The code could be found on my GitHub or here:

def insertion_sort_optimized(arr):
    array = [arr[0]]
    for i in range(1, len(arr)):
        index = bisect_left(array, i)
        array.insert(index, i)
    return array

And then I implememented Quicksort as usually (link):

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    smaller_part = []
    larger_part = []
    pivot = arr[len(arr) - 1]
    for i in range(len(arr) - 1):
        if arr[i] < pivot:
            smaller_part.append(arr[i])
        else:
            larger_part.append(arr[i])
    return quicksort(smaller_part) + [pivot] + quicksort(larger_part)

And then I generated a random array of 1.000.000 numbers and compared the performance of both of them, using this helper function:

def test_sorting_algorithm(sort=None, version="normal", returns=False, n=1000000):
    if version.lower() == "normal":
        print("Normal version:")
    else:
        print("Optimized version:")
    arr = [int(random() * n) for _ in range(n)]
    print(arr)

    start = time.time()
    if returns:
        arr = sort(arr)
    else:
        sort(arr)
    end = time.time()

    print(arr)
    print(f"Time elapsed: {end - start}n")

So it basically runs the given sort function and prints how much time did it take to sort the array. And so I ran this code for at least 10 times and the binary insertion sort was almost 9 times faster (9s > 1s) each time. But I thought that the Quicksort was the fastest… And if I compare those 2 sorting algorithms, I would say that binary insertion sort is better, although it takes O(n) additional space (worst time complexity would be O(n*log(n)) which is better than Quicksort…). Is it a mistake? Is Quicksort actually worse than binary insertion sort? I tried to find it all over the Internet but couldn’t find something really similar to my code. Maybe it is not even binary insertion sort, but rather something else…(another name)?

Answer

Let’s look at your attempt to write insertion sort:

def insertion_sort_optimized(arr):
    array = [arr[0]]
    for i in range(1, len(arr)):
        index = bisect_left(array, i)
        array.insert(index, i)
    return array

You’re not inserting the array values, you’re inserting the indexes. In increasing order. So this is wrong and it’s O(n log n), instead of the O(n^2) that a correct version would take (due to the linear time for each insert).

Advertisement

Answer