Today I will show the way I have implemented the Insertion Sort algorithm.
Insertion sort is a simple sorting algorithm that sorted partition grown from left to right.
Split the array to two parts: sorted partition and unsorted partition. The algorithm will make the sorted partition grows from left to right.
The first element of the array (index = 0) will belong to sorted partition.
Traverse the array from the second element (index = 1) to the last element of the array. We traverse the array by ascending order, btw. The part from a[1..n] is unsorted partition.
Each of iteration, large comparison the first element of unsorted partition versus the last right elements of sorted partition.
Another loop will look through the sorted partition by descending way, and then shift right elements of sorted partition to one position ahead of their current position.
- The algorithm ends when there is no element in unsorted partition means the outside loop hit to last element of the array.
int length = arr.length;