Knowledge of selection sort is not required to understand insertion sort. This resource makes references selection sort to contrast the algorithms. Insertion sort is slightly more complex than selection sort and is often studied after selection sort.
Insertion sort algorithm & trace
Insertion sort logically partitions the array into 2 parts. The pipe character (|) represents the partition in this example. The partition is a logical structure. Nothing is physically inserted into the array.
The properties below are true before and after each pass (though not necessarily in the middle of each pass). More formally, the conditions below are the loop invariant for insertion sort.
- Everything to the left of the
|is sorted. (This is a different statement than for selection sort.) - Everything to the right of the
|is unchecked. (This is the same statement as for selection sort.)
With each pass, insertion sort inserts the first element in the unchecked part into its correct position in the sorted part. Each element already in the sorted part that must be moved is copied one spot to the right.
Before the first pass
[37 | 32 70 15 93 40 63 3 40 63]
The partition starts after the first element. The properties above are both true. There is only 1 element to the left of the |, so the left side is sorted.
Unlike with selection sort, the elements in the sorted part are not necessarily in their final positions.
Pass 1: inserting 32
Before finding insertion position
[37 | 32 70 15 93 40 63 3 40 63]
elementToInsert: 32
The first element in the unchecked part (32) is copied into the variable elementToInsert. The actual value of the element is copied, not the index.
After finding insertion position but before insertion
[37 | 37 70 15 93 40 63 3 40 63]
^
insertion position
elementToInsert: 32
elementToInsert is to be inserted into its correct position in the sorted part. Moving from right to left, elementToInsert is compared against each element in the sorted part until the correct position is found. If elementToInsert is less than the element in the sorted part, the element in the sorted part is copied one spot to the right to make room for elementToInsert. The elements are not swapped.
In the example, 37 is copied one spot to the right.
The insertion position is found because index 0 is reached.
After insertion
[32 37 | 70 15 93 40 63 3 40 63]
^
insertion position
elementToInsert: 32
elementToInsert is copied to the insertion position, replacing the element originally at that position.
The sorted part is 1 larger than it was before the pass. The properties above are again true.
In the example, 32 replaces 37.
Pass 2: inserting 70
Before finding insertion position
[32 37 | 70 15 93 40 63 3 40 63]
elementToInsert: 70
70 is the first element in the unchecked part and is copied into elementToInsert.
After finding insertion position but before insertion
[32 37 | 70 15 93 40 63 3 40 63]
^
insertion position
elementToInsert: 70
The insertion position is found because 70 is not less than 37.
70 is already in its correct position. This is not a special case and no additional code is required to handle it.
After insertion
[32 37 70 | 15 93 40 63 3 40 63]
^
insertion position
elementToInsert: 70
Insertion sort copies elementToInsert to the insertion position as with any other pass. In this case, it replaces 70 with 70.
Pass 3: inserting 15
Before finding insertion position
[32 37 70 | 15 93 40 63 3 40 63]
elementToInsert: 15
After finding insertion position but before insertion
[32 32 37 | 70 93 40 63 3 40 63]
^
insertion position
elementToInsert: 15
The elements 70, 37, and 32 are each copied one spot to the right, in that order.
The insertion position is found because index 0 is reached.
After insertion
[15 32 37 70 | 93 40 63 3 40 63]
^
insertion position
elementToInsert: 15
The first copy of 32 is replaced with 15.
Pass 4: inserting 93
Before finding insertion position
[15 32 37 70 | 93 40 63 3 40 63]
elementToInsert: 93
After finding insertion position but before insertion
[15 32 37 70 | 93 40 63 3 40 63]
^
insertion position
elementToInsert: 93
The insertion position is found because 93 is not less than 70.
After insertion
[15 32 37 70 93 | 40 63 3 40 63]
^
insertion position
elementToInsert: 93
93 is replaced with 93. Replacing the element with a copy of itself is faster and less error prone than checking if the replacing is necessary.
Pass 5: inserting 40
Before finding insertion position
[15 32 37 70 93 | 40 63 3 40 63]
elementToInsert: 40
After finding insertion position but before insertion
[15 32 37 70 70 | 93 63 3 40 63]
^
insertion position
elementToInsert: 40
The elements 93 and 70 are each copied one spot to the right, in that order.
The insertion position is found because 40 is not less than 37.
After insertion
[15 32 37 40 70 93 | 63 3 40 63]
^
insertion position
elementToInsert: 40
The 70 originally at the insertion position is replaced with 40.
Remaining passes
[15 32 37 40 70 93 | 63 3 40 63]
[15 32 37 40 63 70 93 | 3 40 63]
[3 15 32 37 40 63 70 93 | 40 63]
[3 15 32 37 40 40 63 70 93 | 63]
[3 15 32 37 40 40 63 63 70 93 |]
The process repeats until after the last element is inserted.
Note that insertion sort does NOT copy the array. The array is copied here only to show the progression.
The statements at the top of the page are true following each pass through the array.
Insertion sort skips the first element. Selection sort skips the last element.
Insertion sort implementation
public static void sort(int[] arr)
{
for (int i = 1; i < arr.length; i++)
{
int elementToInsert = arr[i];
int j = i;
while (j > 0 && elementToInsert < arr[j - 1])
{
arr[j] = arr[j - 1];
j--;
}
arr[j] = elementToInsert;
}
}
Insertion sort is typically implemented with a while loop nested inside a for loop. The inner loop is responsible for finding the position at which elementToInsert should be inserted and for moving the necessary elements out of the way. The outer loop inserts elementToInsert into the correct position and tracks the partition.
At the beginning of each pass of the outer loop, i is the index of the first element of the unchecked part. At the end of each pass, i is the index of the last element of the sorted part.
j serves 2 related purposes. j is used by the inner loop to traverse the sorted part. After the inner loop, j is the index of the insertion point.
Alternative usage of j
public static void sort(int[] arr)
{
for (int i = 1; i < arr.length; i++)
{
int elementToInsert = arr[i];
int j = i - 1;
while (j >= 0 && elementToInsert < arr[j])
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = elementToInsert;
}
}
Beginning programmers often start j at i - 1 since the value at i - 1 is the first value that must be checked by the inner loop. In this case, j is the index of the element to be compared against elementToInsert.
This is acceptable as long as the all lines use j consistently. The code above is correct.
Insertion sort variants
Recursive implementation (works)
// inserts value into correct position in arr[0] ... arr[index]
// precondition: arr[0] ... arr[index - 1] is sorted &&
// arr[index] == value
private static void insert(int[] arr, int value, int index)
{
if (index == 0 || value >= arr[index - 1])
{
arr[index] = value;
return;
}
arr[index] = arr[index - 1];
insert(arr, value, index - 1);
}
// sorts arr[index] ... arr[arr.length - 1]
public static void sort(int[] arr, int index)
{
if (index >= arr.length)
return;
insert(arr, arr[index], index);
sort(arr, index + 1);
}
public static void sort(int[] arr)
{
sort(arr, 1);
}
This variant uses 2 private helper methods and a public method:
insertis equivalent to the code inside the outer loop in the iterative implementation.inserttakes the first element in the unchecked part and inserts it into the sorted part.sort(int[], int)is the private recursive helper method forsort(int[]).sort(int[], int)recursively sorts the part of the array starting at its parameterindex.sort(int[])is the public method. It calls the recursive helper method.sort(int[])exists because this is the appropriate public method header for a sort method.
It is unlikely that this variant would be featured on the AP CS A Exam. The variant is presented here to improve understanding of the algorithm and as a demonstration of recursion. The sort(int[]) method shows the insertion sort algorithm elegantly.
- Insert the first element of the unchecked part into the sorted part.
- Sort the rest of the array.
Insertion sort using binary search
public static void sort(int[] arr)
{
for (int i = 1; i < arr.length; i++)
{
int elementToInsert = arr[i];
int insertionPoint = binarySearch(arr, elementToInsert, 0, i - 1);
if (insertionPoint < 0)
insertionPoint = -(insertionPoint + 1);
for (int j = i - 1; j >= insertionPoint; j--)
arr[j + 1] = arr[j];
arr[insertionPoint] = elementToInsert;
}
}
The call to binarySearch refers to the method on my binary search page under Binary search with insertion point return. The description on that page explains what the method returns.
This variant of insertion sort uses binary search to find the position at which elementToInsert should be inserted into the sorted part of arr. This variant then uses a for loop to move the elements that need to be moved to make room for elementToInsert. The insertion itself is done normally.
This is likely too complicated for an AP CS A Exam question; however, it provides an additional opportunity to understand the behavior of insertion sort.
This approach makes fewer comparisons than the original version; however, it must still loop through the same number of elements in the sorted part to move those elements. The additional complexity of calling binary search means this is unlikely to be used in practice. In practice, the original version of insertion sort is often used as a base case for an algorithm such as merge sort. Merge sort runs quickly on a large number of elements but slowly on a small number of elements.
Insertion sort with binary search with ArrayList<String>
public static void sort(ArrayList<String> list)
{
for(int i = 1; i < list.size(); i++)
{
int position = binarySearch(list, list.get(i), 0, i - 1);
if (position < 0)
position = -(position + 1);
list.add(position, list.remove(i));
}
}
This is an interesting variant because its apparent simplicity hides complexity. There is no need for a loop to shift elements over to make room to insert the element at i. The variant doesn’t even require a variable to store a copy of the element. Instead, the ArrayList remove and add methods handle the shift. Unfortunately, the calls to remove and add are quite expensive, so this variant is unlikely to be used in practice.