Insertion Sort

1. Overview

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. It's one of the Greedy Algorithms. For nearly sorted data, consider that insertion sort is O(n) time.

2. Description

2.1 Procedure

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 4 (last element of the array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6

i = 4. 6 will move to the position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13

# Python program for implementation of Insertion Sort 
  
# Function to do insertion sort 
def insertionSort(arr): 
  
    # Traverse through 1 to len(arr) 
    for i in range(1, len(arr)): 
  
        key = arr[i] 
  
        # Move elements of arr[0..i-1], that are 
        # greater than key, to one position ahead 
        # of their current position 
        j = i-1
        while j >= 0 and key < arr[j] : 
                arr[j + 1] = arr[j] 
                j -= 1
        arr[j + 1] = key 
  
  
# Driver code to test above 
arr = [12, 11, 13, 5, 6] 
insertionSort(arr) 
for i in range(len(arr)): 
    print ("% d" % arr[i]) 
  
# This code is contributed by Mohit Kumra 

2.2 Time and Space Complexity

Particular	Complexity
Best	O(n) comparisons, O(1) swaps
Worst	O($n^{2}$) comparisons and swaps
Average	O($n^{2}$) comparisons and swaps
Space	O(n) total, O(1) auxiliary
Algorithm paradigm	Incremental approach
Sorting In Place	Yes
Stable	Yes
Online	Yes

2.3 Application

Insertion sort is used when the number of elements is small. It can also be useful when the input array is almost sorted, only a few elements are misplaced incomplete big array.

3. Reference

https://en.wikipedia.org/wiki/Insertion_sort

https://www.geeksforgeeks.org/insertion-sort/

https://www.youtube.com/watch?v=OGzPmgsI-pQ&feature=emb_title