Complete the Insertion sort practice problem before viewing the solution.

Review the insertion sort practice problem with AP CS Tutor Brandon Horn.

## Insertion sort trace

[37 | 32 70 15 93 40 63 3 40 63] [32 37 | 70 15 93 40 63 3 40 63] [32 37 70 | 15 93 40 63 3 40 63] [15 32 37 70 | 93 40 63 3 40 63] [15 32 37 70 93 | 40 63 3 40 63] [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 elements to the left of the separator (|) are sorted. The elements to the right of the separator are unchecked. The separator starts after the first element. This is possible because a single element is guaranteed to be sorted.

Unlike with selection sort, the elements to the left of the separator are not necessary in their final positions. Instead of placing elements into their final positions, as selection sort does, insertion sort shifts one element at a time into its proper position in the sorted part. No element is guaranteed to be in its final position until the method finishes.

## Insertion sort implementation

```
public static void sort(int[] x)
{
for (int i = 1; i < x.length; i++)
{
int next = x[i];
int j = i;
while (j > 0 && next < x[j - 1])
{
x[j] = x[j - 1];
j--;
}
x[j] = next;
}
}
```