# Insertion Sort

Source: https://wisconsin.twango.dev/fa24-cs300/u3-algorithms/sorting-and-search/sorting/insertion-sort

# Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input array, removing one element at a time and inserting it into its correct position in the sorted array.

## Features
- [x] Stable sorting algorithm
- [x] In-place sorting algorithm

### Pseudocode


```text
procedure insertionSort(A : list of sortable items)
    for i = 1 to length(A) - 1 do
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key do
            A[j + 1] = A[j]
            j = j - 1
        end while
        A[j + 1] = key
    end for
end procedure
```

### Java


```java
public static void insertionSort(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;
    }
}
```

## Runtime Analysis

Given $N$ elements in the array and $K$ inversion pairs, the time complexity of insertion sort is $\Theta(N + K)$.

### Best Case

The best case occurs when the array is already sorted. In this case, the algorithm makes a single pass through the array and does not perform any swaps. The time complexity is $\Omega(N)$.

### Worst Case

The worst case occurs when the array is sorted in reverse order. In this case, the algorithm makes $N-1$ passes through the array, performing $N-1$ swaps on the first pass, $N-2$ swaps on the second pass, and so on. The total number of inversion pairs, $K$ in a reverse-sorted array, is given by:

$$
K = (N-1) + (N-2) + \ldots + 1 = \frac{N(N-1)}{2}
$$

This results in a time complexity of $O(N^2)$.

## Source

The existing course note was retained and normalized during the merge.

Related: [[u3-algorithms/sorting-and-search/index|Topic index]].