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:

`insert`

is equivalent to the code inside the outer loop in the iterative implementation.`insert`

takes the first element in the unchecked part and inserts it into the sorted part.`sort(int[], int)`

is the private recursive helper method for`sort(int[])`

.`sort(int[], int)`

recursively sorts the part of the array starting at its parameter`index`

.`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.