Insertion Sort

Insertion Sort is one of the three "simple sorts" (bubble, selection, insertion). These types of sorting algorithms are all "brute force" and have a Big O (worst-case complexity) for time of n^2.

Insertion Sort is also a "stable" sorting algorithm. Meaning that as it goes through the array of values from left to right, any equal values will have the same (relative) order before and after they are sorted.

Insertion Sort can be done in place; O(1) space complexity. It's best for small lists with around 50 values or less.

Insertion Sort is similar to Selection Sort in some ways, but it's important to understand their differences in complexity in different scenarios. There are various pros/cons for each approach and you will want to choose one over the other depending on context.

Resources

• Insertion Sort
• Why Tailors Use Insertion Sort
• Insertion Sort Wikipedia
• Visual insertion algorithm walk-through