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

Java

Javascript

Python

Doodle

insertion sort doodle

Download Java, JavaScript and Python code
Insertion sort doodle
Selection sort