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. We’ll use a pipe character (|) to represent the partition. (The partition is a logical structure. Nothing is physically inserted into the array.)
- 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.)
Step 1
The partition starts after the first element. The statements 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.
[37 | 32 70 15 93 40 63 3 40 63]
Step 2
The algorithm copies the first element in the unchecked part into a variable.
elementToInsert: 32
Starting with the last element in the sorted part and moving to the left, the algorithm compares elementToInsert against elements in the sorted part until it finds where elementToInset should go to maintain the sorted order.
Each time the algorithm determines that elementToInsert is less than an element in the sorted part, it copies the element in the sorted part 1 position to the right to make room for elementToInsert.
Insertion sort does not swap elements (unlike selection sort). This is a common misconception. Insertion sort copies elements 1 spot to the right in the array.
[37 | 37 70 15 93 40 63 3 40 63]
Insertion sort inserts elementToInsert into its correct position in the sorted part. This could be either at the beginning of the array, somewhere in the middle of the sorted part, or at the end of the sorted part (where elementToInsert started).
[32 37 | 70 15 93 40 63 3 40 63]
The statements above are true following the first pass through the array.
Step 3
elementToInsert: 70
The algorithm checks if elementToInsert, which is 70, is less than 37. Since 70 is not less than 37, the algorithm copies 70 on top of itself.
[32 37 70 | 15 93 40 63 3 40 63]
The statements above are true following the second pass through the array.
Step 4
elementToInsert: 15
Is 15 less than 70? Yes. Copy 70 one spot to the right.
[32 37 70 | 70 93 40 63 3 40 63]
Is 15 less than 37? Yes. Copy 37 one spot to the right.
[32 37 37 | 70 93 40 63 3 40 63]
Is 15 less than 32? Yes. Copy 32 one spot to the right.
[32 32 37 | 70 93 40 63 3 40 63]
We’re at the beginning of the array, so 15 must go at position 0.
[15 32 37 70 | 93 40 63 3 40 63]
Step 5
elementToInsert: 93
Is 93 less than 70? No. The algorithm copies 93 on top of itself.
[15 32 37 70 93 | 40 63 3 40 63]
The statements above are true following this pass through the array.
Step 6
elementToInsert: 40
Is 40 less than 93? Yes. Copy 93 one spot to the right.
[15 32 37 70 93 | 93 63 3 40 63]
Is 40 less than 70? Yes. Copy 70 one spot to the right.
[15 32 37 70 70 | 93 63 3 40 63]
Is 40 less than 37? No. 40 must go at the original position of 70.
[15 32 37 40 70 93 | 63 3 40 63]
The statements above are true following this pass through the array.
Remaining steps
If we repeat this process, we end up with a sorted array. The remaining sequence of steps is shown below. Note that insertion sort does NOT copy the array. The array is copied here only to show the progression.
[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 statements above are true following each pass through the array.
We stop the process after the last element, unlike selection sort which 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 moves the partition.
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; j > insertionPoint; j--)
arr[j] = arr[j - 1];
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.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.