CODEWITHSUNDEEP
pythonalgorithmsortingquicksortinsertion-sort
A. Lee
A. Lee

Reputation: 29

Why is insertion sort so fast compared to other sorting algorithms?

I've been testing the speed of various other sorting algorithms (Selection, Quick, Bubble, Shell, Radix, etc) along with Insertion Sort. However, Insertion Sort seems to be the fastest algorithm by far. I always thought Quick Sort would be the fastest.

Here is my code for the Insertion Sort and Timer functions in Python 3.

def InsertionSort(argShuffledList):
    for index in range(1,len(argShuffledList)):

        currentvalue = argShuffledList[index]
        position = index

        while position>0 and argShuffledList[position-1]>currentvalue:
            argShuffledList[position]=argShuffledList[position-1]
            position = position-1

        argShuffledList[position]=currentvalue
    return argShuffledList

def Timer(argFunction, *args): ## function for timing functions
    dblStart = time.clock()
    argFunction(*args)
    intTime = "%.2f" % ((time.clock() - dblStart) * 1000000)
    message = "Elasped Time: " + str(intTime) + " microseconds"
    return message

insertionSortList = InsertionSort(insertionCopyList) 
timeInsertionSortList = Timer(InsertionSort, insertionCopyList)

Upvotes: 0

Views: 2960

Answers (3)

Paul Hankin
Paul Hankin

Reputation: 58271

You are sorting the list before timing it. So when you time it, the list is already sorted, and your insertion sort needs to do no insertions, so runs in linear time.

insertionSortList = InsertionSort(insertionCopyList) 
timeInsertionSortList = Timer(InsertionSort, insertionCopyList)

It's not clear what the intention of the first call to InsertionSort is, unless you're trying to time already-sorted lists.

Upvotes: 2

FluxIX
FluxIX

Reputation: 325

The "best" sort for a task is dependent on a number of criteria including data type, number of items, data distribution, etc.

The number of items matters because the simpler O(n^2) sort algorithms have much less overhead than the more process-efficient O(n lg n) algorithms, but the overhead becomes much less significant the more items you have to sort. This is why at least one implementation of qsort which Microsoft shipped with Visual C++ used a quicksort until a given partition had seven or less items, at which point the partition was sorted using an insertion sort.

Insertion sort is faster than some of the other O(n^2) sort algorithms because it has less overhead (especially when compared with bubble sort).

There are also variations of sorting algorithms. For example, a two-partition quicksort has a worse worst-case performance than the more complex three-partition quicksort, especially if the data was already sorted in reverse-order.

Radix sort is a special sort whose performance greatly relies on the data type. It is best used when the data items are fixed-width and this fact can be leveraged, which makes it great for sorting lists of integers but not for sorting lists of general strings. I have seen work someone did to make it efficient for sorting (32-bit) floating-point, but it did heavily leverage the internal storage of the floating-point number.

Upvotes: 2

Joseph Chotard
Joseph Chotard

Reputation: 695

It actually depends on what type of list you are using: even though Insetrion Sort's worst-case time is O(n2) it is an approximation meaning that it does not apply for small or nearly sorted lists.

Quick sort uses extra overhead because of all the recursive functions. This is why you should privilege Insertion sort over the divide and conquer sorting algorithms like merge sort and quick sort when the problem is small.

Upvotes: 0

Related Questions