insertion-sort.asc

Insertion Sort

Insertion sort is a simple sorting algorithm. It is one of the most natural ways of sorting. If I give you some cards to sort, you will probably use this algorithm without knowing.

Insertion Sort Implementation

Insertion sort does the following: It starts from the 2nd element, and it tries to find anything to the left that could be bigger than the current item. It will swap all the elements with higher value and insert the current element where it belongs.

Insertion sort

link:../../../src/algorithms/sorting/insertion-sort.js[role=include]

1. Convert to an array or clone the array.

2. Start with the 2nd element. Everything on the left is considered sorted.

3. Compare the current element (2nd) to the previous one. If left - 1 is bigger, it will swap places. If not, it will continue checking the next one to the left.

4. We check every element on the left side and swap any of them that are out of order

Insertion Sort Properties

• [Stable]: ✅ Yes

• [In-place]: ✅ Yes

• [Online]: ✅ Yes

• [Adaptive]: ✅ Yes

• Time Complexity: ⛔️ part01-algorithms-analysis.asc O(n²)

• Space Complexity: ✅ part01-algorithms-analysis.asc O(1)