Why does the index J start at 1?
The single integer at index 0 is already a sorted sub-list.
Why does the index J end at length-1?
The very last integer in the list at index length-1 must be inserted into the sub-list. (Unlike with selection sort, it is not automatically in order.)
Here is insertion sort coded in Java:
public static void insertionSort (int[] list) { // For each unsorted integer for (int j = 1; j < list.length; j++) { // Keep swapping with its left neighbor // until it is larger or equal to left neighbor int k = j; while (k > 0 && list[k-1] > list[k] ) { int temp = list[k-1]; list[k-1] = list[k]; list[k] = temp; k--; } } }
Here is the informal description of the algorithm (repeated from above):
Input: A list of integers.
Output: The list is sorted.
Assume that the sub-list of just one integer at index 0 is sorted
for each index J of the list from 1 to length-1
Insert the integer at index J into the sorted sub-list.
Do this by repeatedly swapping it with its neighbor to the left until it is in the correct place.
It is in the correct place when its left neighbor is smaller than it, or if there is no left neighbor.
Why does the condition of the while
loop check that k>0
?