Insertion Sort repeatedly removes an element from the input data and inserts it into the position so that its value is between the previous and the next element. It works the way we sort when playing cards. O(n 2) average and worst. Insertion sort is the best of simple sorting. For random data this algorithm runs twice as fast as the bubble sort and faster than selection sort.

insertion sort

Table of Content


What is insertion sort?

Insertion sort works the same way as we play cards. When we grad a new card from a deck, we insert it into the right place so that all cards in our hand are ordered. The time complexity is O(n 2) time.

How to implement insertion sort ?

Insertion sort uses a for loop to iterate through each element starting from index 1 in an array. Inside the loop, you use a while loop to check previous elements before the current item. Insert the current element in a position so that all elements before current position are sorted.


Insertion sort visualization

insertion sort doodle


Insertion sort code

Java

Javascript

Python


Free download

Download Java, JavaScript and Python code
Algorithm types and algorithm examples