Introduction to Insertion Sort
Insertion sort is a stable, in-place sorting algorithm that
builds the final sorted array one item at a time. It is not the very best in terms
of performance but more efficient traditionally than most other simple O(n2) algorithms
such as selection sort or bubble sort. Insertion sort is can be used within the same array
but is more clear if the sorted output is put in a separate "template" array instead.
How to perform: Insertion Sort
- Iterate through the list
- Take the second unsorted index and compare the data with the data at first index
- Swap if data at second index is smaller
- Take the next unsorted index and compare it with the data to the left of it
- Swap if compared data is larger than the data at unsorted index
- Repeat steps 4-5 until the entire list has been iterated over
Example of Insertion Sort
