Insertion Sort

What Is It?

• Insertion Sort builds the sorted portion of the array one element at a time.

• It starts by treating the first element as “sorted.”

• Then it takes the next element and “inserts” it into the correct position among the already-sorted elements.

• This repeats for each element in the array until everything is sorted.

Key Points

• Great for small or nearly sorted arrays because it’s easy to implement.

• Worst-case time complexity: O(n²).

Insertion Sort: Step by Step

Idea: In Insertion Sort, we treat the array in two parts: a “sorted” portion (on the left) and an “unsorted” portion (on the right). We take the first unsorted element and insert it into its correct spot among the sorted elements.