Hire The World’sTop Talent On Demand
Full-stack DevelopersFront-end DevelopersSoftware DevelopersWeb DevelopersMobile App DevelopersAI EngineersAndroid DevelopersAngularJS DevelopersDjango DevelopersDrupal DevelopersGame DevelopersHadoop DevelopersiOS DevelopersJava DevelopersJavaScript DevelopersMagento DevelopersNode.js DevelopersPHP DevelopersPostgreSQL DevelopersPython DevelopersReact.js DevelopersSalesforce DevelopersScala DevelopersUnity DevelopersWordPress DevelopersAPI DevelopersRuby on Rails DevelopersKubernetes Developers
Toptal connects the top 3% of freelance developers all over the world.
Insertion Sort
Animation, code, analysis, and discussion of insertion sort on 4 initial conditions.
How to use: Press "Play all", or choose the 
button.
ALGORITHM
for i = 2:n,
for (k = i; k > 1 and a[k] DISCUSSION
Although it is one of the elementary sorting algorithms with O(n2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).
For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.
KEY
- Black values are sorted.
- Gray values are unsorted.
- A red triangle marks the algorithm position.
PROPERTIES
- Stable
- O(1) extra space
- O(n2) comparisons and swaps
- Adaptive: O(n) time when nearly sorted
- Very low overhead