Insertion Sort

What is insertion sort?

Insertion sort is a sorting Algorithm that work from left to right :

1. Assuming the first element is already sorted.

2. Compare the second element with the first element if the second element is smaller than the first element then swap them.

3. Move to the third element ,compare it with the first two and put it on it's correct position.

4. Continue the process until the array is sorted.

Manually Trace:

C Programme:

Time complexity of insertion sort is :

Best case: O(n)

Worst case: O(n²)