Data Structures & Algorithms

Insertion Sort

Insertion sort is one of the simplest sorting algorithms. In this post, we will cover the insertion sort algorithm, the input and output for the algorithm, implementation in python and time complexity for the algorithm. The algorithm takes in a sequence of numbers as input and sorts the numbers to produce an ordered sequence sorted from smallest to largest as output.

The algorithm sorts by picking each number one at a time, from the smallest to largest index and inserting it in the correct index (hence the name insertion sort). A number is in the correct index if the numbers to its left are smaller than that number. For each number in an index, the algorithm checks whether the number to the left is lesser than that number or not. If it is lesser, the algorithm moves to the next index.

Otherwise, it finds a position such that the element to its left is smaller than that number. To insert the current number in that new position, it right shifts all the larger numbers by one position to make space and then inserts the number in that new position.

The algorithm is described in the following steps:

Step 1:

If the index is 1, increment index go to step 2.

Step 2:

Pick the element. If the element is none, return.

Step 3:

Compare it to the element in the previous index.

Step 4:

If the element is lesser than the element in the previous index, find a position such that all the elements to the left of the new position are smaller than that element. Otherwise increment index and go to step 2.

Step 5:

Shift all the elements greater than that element and are to the left of the element’s current index one position to the right.

Step 6:

Insert the element in the new position. Increment index and go to step 2.

Source Code

def insertion_sort(arr, n):

    # From second position

    for i in range(1, n):


        # Pick the element

        key = arr[i]

        j = i - 1

       

        # Find an index such that all element to the left are

        # smaller than that number

        while((arr[j] > key) and (j >= 0)):

            # Right shift the greater elements by one index

            arr[j+1] = arr[j]

                 j = j - 1

        # Insert the element

        arr[j+1] = key

    return arr


if __name__ == "__main__":

    arr = [2, 1, 8, 6, 4]

    n = len(arr)

    arr = insertion_sort(arr, n)

    print (arr)

The following table shows sorting of the sequence [2, 1, 8, 6, 4]

Initial array: [2, 1, 8, 6, 4]

Iteration 1:

[1, 2, 8, 6, 4]

Iteration 2:

[1, 2, 8, 6, 4]

Iteration 3:

[1, 2, 6, 8, 4]

Iteration 4:

[1, 2, 4, 6, 8]

In iteration k, the element in position k+1 is sorted (we begin at second position). Hence, after k iteration, elements from 1…k+1 will be sorted and after n-1 iterations, where n is the number of elements in the input, all elements will be sorted.

The outer for loop runs over all the elements and inner while loop runs over elements which are only greater than the current element and present to the left of the current element. The inner loop has a linear time of O(n).

The best-case running time of insertion is when all the elements are already sorted in the input. Hence, it will take O(n) (linear time) because in each iteration we compare the element with the previous element and since the previous element will be lesser than the current element, the algorithm moves to the next position and the inner loop is not called.

The worst-case time complexity arises when the elements are in reverse order. In this case, the second element has to be moved 1 position left, the third element has to be moved two positions left, until the last element which has to be moved n-1 positions left. This will take quadratic time complexity (O(n^2)).

The average case time complexity of insertion sort is also quadratic. Hence, insertion sort is inefficient for inputs of large size. But the algorithm is the most efficient for small input sizes. The sorting takes place in-place in insertion sort and hence, no additional space is required.

About the author

Arun Palaniappan