Insertion Sort

Key Idea

This is probably the most intuitive sorting algorithm. If you have played poker before, then this is your go-to algorithm to sort cards in your hand.

Code

public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        // all cards before i are sorted
        insert(arr, i);
    }
}

private void insert(int[] arr, int newbie) {
    for (int i = newbie; i > 0 && arr[i] < arr[i-1]; i--) {
        swap(arr, i, i-1);
    }
}

Time Complexity

The worst case analysis in bubble sort, selection sort, and insertion sort all share a common theme - a halved square (a rugged triangle). That triangle is proportional to O(n^2).