Insertion Sort


Characteristics

Simple implementation

Insertion sort can be implemented easily with less lines of code. It is quite efficient for small data sets. Though it has same complexity than other quadratic sorting algorithms like selection sort or bubble sort, insertion sort is more efficient.

Adaptive

Insertion sort is adaptive. If the input data set is already sorted, the number of steps are reduced.

Online

Insertion sort works on the data as it receives it. The dataset is always sorted in each step of the insertion sort. A practical example of insertion sort is sorting a hand of playing cards. Assume, at the beginning of a card game, we have no cards in the left hand. Then we take a face down card from the table and search for it's position in the left hand. To find the correct position for a card we compare the newly drawn card with each of the cards in the left hand from left to right. Then when we find the suitable spot, we insert the card into it's correct position. At any times, the cards in the left hand are sorted.

Stable

Insertion sort is stable. Numbers with the same value appears in the output array as they appear in the input array. Let's take an input array A = [3, 0, 3]. In the input array the value 3 occurs 2 times; at index 0 and 2. Insertion sort ensures that in the output array the occurrences of 3 are placed as same order as of the input array.

In place:

Insertion sort sorts the input list in place. It does not require additional list to sort the elements. It only requires a constant amount of additional memory space O(1).

Quadratic time complexity

It has a quadratic time complexity.

  • Worst Time complexity (Big-O): O(n*n), where n: total number of elements in the list.
  • Average Time complexity (Big-Theta): Θ(n*n), where n: total number of elements in the list.
  • Best Time complexity (Big-Omega): Ω(n), where n: total number of elements in the list.
  • Space complexity: O(1)

Algorithm Pseudocode

Insertion_Sort(A)
    for i=1 to A.length-1
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = value

Implementation using Python 3

"""
Implementation of insertion sort with test cases
"""

def get_sorted_numbers(numbers):
    """ Returns sorted list for a given list

    Arguments:
    numbers -- list of numbers
    """
    for i in range(1, len(numbers)):
        j = i-1
        value = numbers[i]
        while j >= 0 and numbers[j] > value:
            numbers[j+1] = numbers[j]
            j -= 1
        numbers[j+1] = value
    return numbers


if __name__ == "__main__":
    test_numbers = [2, 3, 1, 4, 2, 4]
    sorted_numbers = sorted(test_numbers)
    assert sorted_numbers == get_sorted_numbers(test_numbers), "Failed on {}".format(test_numbers)

    test_numbers = [2, -3, 1, -4, 2, 4]
    sorted_numbers = sorted(test_numbers)
    assert sorted_numbers == get_sorted_numbers(test_numbers), "Failed on {}".format(test_numbers)

    test_numbers = [1, 1, 1, 1]
    sorted_numbers = sorted(test_numbers)
    assert sorted_numbers == get_sorted_numbers(test_numbers), "Failed on {}".format(test_numbers)

    test_numbers = [1]
    sorted_numbers = sorted(test_numbers)
    assert sorted_numbers == get_sorted_numbers(test_numbers), "Failed on {}".format(test_numbers)

    test_numbers = [1, 0, -1]
    sorted_numbers = sorted(test_numbers)
    assert sorted_numbers == get_sorted_numbers(test_numbers), "Failed on {}".format(test_numbers)

    test_numbers = [-1, -1, -1]
    sorted_numbers = sorted(test_numbers)
    assert sorted_numbers == get_sorted_numbers(test_numbers), "Failed on {}".format(test_numbers)

    test_numbers = [-1, -3, -56]
    sorted_numbers = sorted(test_numbers)
    assert sorted_numbers == get_sorted_numbers(test_numbers), "Failed on {}".format(test_numbers)

    test_numbers = [-1.5, 3.336, -66.3, 5]
    sorted_numbers = sorted(test_numbers)
    assert sorted_numbers == get_sorted_numbers(test_numbers), "Failed on {}".format(test_numbers)

Difference between Insertion Sort and Counting Sort

  • Insertion sort is a quadratic sorting algorithm where as counting sort uses linear time to sort a set of unsorted integers.
  • Insertion sort's worst case performance is O(n*n) where as counting sort's worst case performance is O(k+n) [Insertion sort - Wiki][Counting sort - Wiki].
  • Though insertion sort has worse time complexity than the counting sort, it is more memory efficient. It requires only O(1) constant space where as counting sort requires O(k+n) space.
  • Another import difference between this two sorting algorithms is the online characteristics. Insertion sort works on live feeding data but counting sort works only after gathering full dataset.

The following table shows the comparison between insertion sort and counting sort based on the execution time.

Set Size Maximum Value Insertion Sort Time Counting Sort Time
10 10 0.012800 seconds 0.023451 seconds
10000 1000 16.564228 seconds 14.874369 seconds

This result is generated using timeit module of Python with the following code.

"""
Compare execution time between insertion sort and counting sort
"""
from timeit import timeit
import random


def get_insertion_sort_sorted_list(numbers):
    """ Returns a sorted list of numbers using insertion sort

    Arguments:
    numbers -- list of numbers
    """
    for i in range(1, len(numbers)):
        value = numbers[i]
        j = i - 1
        while j >= 0 and numbers[j] > value:
            numbers[j+1] = numbers[j]
            j -= 1
        numbers[j+1] = value
    return numbers


def get_counting_sort_sorted_list(numbers, max_value):
    """ Returns a sorted list of non negative using counting sort

    Arguments:
    numbers -- list of non negative integers within max_value
    max_value -- non negative integer
    """
    sorted_numbers = [None] * len(numbers)
    counts = [0] * (max_value+1)
    for i in numbers:
        counts[i] += 1
    counts[0] -= 1
    for i in range(1, max_value+1):
        counts[i] += counts[i-1]
    for i in numbers[::-1]:
        sorted_numbers[counts[i]] = i
        counts[i] -= 1
    return sorted_numbers


if __name__ == "__main__":
    MAX_NUMBER = 10
    small_list = [random.randint(0, MAX_NUMBER) for i in range(10)]
    insertion_execution_time = timeit('result=get_insertion_sort_sorted_list(small_list)',
                                      globals=globals(), number=10000)
    counting_execution_time = timeit('result=get_counting_sort_sorted_list(small_list, MAX_NUMBER)',
                                     globals=globals(), number=10000)
    print("Insertion sort took: {} seconds".format(insertion_execution_time))
    print("Counting sort took: {} seconds".format(counting_execution_time))

    MAX_NUMBER = 1000
    medium_list = [random.randint(0, MAX_NUMBER) for i in range(10**4)]
    insertion_execution_time = timeit('result=get_insertion_sort_sorted_list(medium_list)',
                                      globals=globals(), number=10000)
    counting_execution_time = timeit('result=get_counting_sort_sorted_list(medium_list, MAX_NUMBER)',
                                     globals=globals(), number=10000)
    print("Insertion sort took: {} seconds".format(insertion_execution_time))
    print("Counting sort took: {} seconds".format(counting_execution_time))

Practice challenges

Easy difficulty challenges:

Reference