Insertion sort
›Short versionOpen if you only have a minute.
- The left side stays sorted. Each new key slides left until it sits in order, and the larger values shift one place right.
- The sort is stable when the slide stops on an equal key. The comparison is strict greater-than, so the new key stays to the right of earlier equals.
- It is in-place. Extra memory is the key being inserted and the index that walks left.
- A reversed array shifts every prefix and takes quadratic time. An array that is already sorted is one left-to-right pass, linear time.
- Timsort, which Arrays.sort uses for objects, insertion-sorts short runs and then merges them. A whole collection still goes to Arrays.sort. Primitive arrays use a dual-pivot quicksort.
A sorted prefix, one key at a time
Index 0 is a sorted prefix of length one. At step i the value arr[i] is lifted into key. Every larger value in the prefix moves one slot right, opening a hole. The hole closes when the loop finds a value less than or equal to key, or when it reaches the start of the array.
On [4, 3, 2, 10] the key 3 shifts 4 right, the key 2 shifts both of them, and 10 is already larger than the prefix, so it stays. The prefix is sorted at the start of every step. That is the invariant.
Stable, in-place, and sensitive to order
Insertion sort is a . The condition arr[j] > key refuses to move an equal neighbor. The new key is written one place to its right, which is the order the two keys had in the input.
The algorithm is . Cost follows how far each key travels. A reversed array moves the key all the way to index 0 on every step, about n² / 2 shifts, and that is the worst case. An already sorted array performs one comparison per element and no shift, which is linear. A few inversions cost work proportional to those inversions, which is why the sort is called adaptive.
The inner loop used >= instead of >. Where does a new 3 land relative to a 3 already in the prefix?
To the left of the earlier 3. Greater-than-or-equal treats the equal prefix entry as something to shift, so the new key keeps moving. With a strict greater-than test the loop stops, and the new 3 is written to the right of the one that was already there.
When the library sort takes over
Sorting an entire list by hand with insertion sort pays quadratic time as soon as the data is disordered. Call Arrays.sort. Object arrays, and Collections.sort, run . Primitive arrays run a dual-pivot quicksort, again with insertion sort only on tiny partitions. The full insertion sort below is the right tool when you are studying the shift, or when you own a tiny, nearly ordered array and you have a reason to sort it yourself.
public class InsertionSort {
static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6};
sort(arr);
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}