Insertion sort is an algorithm to arrange the elements of a data structure, such as an array or list, in increasing or decreasing order. The algorithm partitions the array into sorted and unsorted parts and repeatedly inserts the first element of the unsorted part into its correct position in the sorted part.

On the AP Computer Science Exam, you must recognize the algorithm when it is presented in code. You may be expected to compare the efficiency to selection sort. You must also be able to recognize a variation of the algorithm such as sorting in decreasing order or sorting from back to front.

## Insertion sort trace

Show each step as insertion sort is run on the array below.

[37 32 70 15 93 40 63 3 40 63]

At each step, separate the sorted and unsorted parts with the | symbol.

## Insertion sort implementation

Method sort arranges the elements in x in increasing order using the insertion sort algorithm.

Complete method sort below.

public static void sort(int[] x)

See the Insertion sort practice problem solution or review it with AP CS Tutor Brandon Horn.