This algorithm is smarter than bubble sort and selection sort. The main idea of the algorithm is as follows:

- Take the
*i*-element from the array. - Swap the elements, starting with element
*i*back to the beginning of the array, until they are in order.

The time complexity is also *O*(*n*^{2}), but for small arrays this algorithm is faster than quick sort or merge sort.

```
import java.util.Arrays;
public class ImplementInsertionSort {
public static void insertionSort(int[] nums) {
int i = 1;
while (i < nums.length) {
int j = i;
while (j >= 1 && (nums[j] < nums[j - 1])) {
var buf = nums[j];
nums[j] = nums[j - 1];
nums[j - 1] = buf;
j--;
}
i++;
}
}
public static void main(String[] args) {
var numbers = new int[]{10, 9, 1, 2, 3, 4, 5, 6, 1};
System.out.println(Arrays.toString(numbers));
insertionSort(numbers);
System.out.println(Arrays.toString(numbers));
}
}
```