You have played card games in our hands in the same insertion sort works. It is a simple sorting algorithm.

Simple word looks interesting to you. It seems to be beginner level concept. Ya, You are thinking right about this algorithm.

## Algorithm for Insertion Sort

// Sort an lst[] of size n insertion_sort(lst) Loop from i = 1 to n-1. Pick element lst[i] and then insert it into sorted sequence lst[0…i-1]

Oh, Programming is simple then its look like 🙂

## Insertion Sort in Python Code

# Insertion Sort Published on Freshlybuilt.com def insertion_sort(lst): # Traverse through 1 to len(lst) for i in range(1, len(lst)): # Move elements of lst[0..i-1], that are # greater than next_elem, to one position ahead # of their current position j = i - 1 next_elem = lst[i] # Compare the current element with next one while lst[j] > next_elem and j >= 0: lst[j + 1] = lst[j] j = j - 1 lst[j + 1] = next_elem print("Iteration number {i}:", lst) return lst def main(): lst = [8, 17, 3, 9] print("Initial Unsorted List:", lst) insertion_sort(lst) print("After Sorting:", lst) if __name__ == "__main__": main()

### Output

Initial Unsorted List: [8, 17, 3, 9] After Sorting: [3, 8, 9, 17]

Okay, But do you have something else for explanation of insertion sort?

Ya, Control Flow Chart( Flowchart) for insertion sort in Python Waiting for your reading.

We have 1:50 min Youtube video for insertion sort in python with given code. Our Main focus is to produce all video less than 5 min 🙂

## Some Facts about Insertion Sort

Time Complexity | O(n*2) |

Auxiliary Space | O(1) |

Sorting In Place | Yes |

Stable | Yes |

Online | Yes |

Algorithmic Paradigm | Incremental Approach |

Boundary Cases: | It will takes maximum time to sort if elements are sorted in reverse order. And Insertion Sort takes minimum time (Order of n) when elements are already sorted. |

**Use** of Insertion Sort

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

**What is Binary Insertion Sort?**

Insertion Sort can use binary search to reduce the number of comparisons in normal insertion sort. Binary Insertion Sort uses binary search to find the proper location to insert the selected item at each iteration. In normal insertion, sorting takes O(i) (at ith iteration) in the worst case. We can reduce it to O(log) by using binary search.

The algorithm, as a whole, still has a running worst-case running time of O(n2) because of the series of swaps required for each insertion.

If you liked my blog, Please like and share it with your friend 🙂

You must be logged in to post a comment.