> For the complete documentation index, see [llms.txt](https://tanias-workspace.gitbook.io/tanias-little-corner/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tanias-workspace.gitbook.io/tanias-little-corner/algorithms/insertion-sort.md).

# Insertion Sort

Insertion Sort builds the final sorted array one item at a time. It picks elements from the unsorted portion and inserts them into their correct position in the sorted portion.

**Steps**:

1. Start with the second element (assume the first element is sorted).
2. Compare it with elements in the sorted portion.
3. Move larger elements one position up to make space.
4. Insert the element into its correct position.
5. Repeat for the rest of the elements.

<figure><img src="/files/hutCnB1Aswf1rkC9PhNZ" alt="" width="375"><figcaption></figcaption></figure>

```cpp
#include <vector>
#include <iostream>

void insertionSort(std::vector<int> &arr) {
    int n = arr.size();
    for (int i = 1; i < n; 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;
    }
}

int main() {
    std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    insertionSort(arr);
    for (int num : arr) std::cout << num << " ";
    return 0;
}
// Some code
```

**Insertion Sort**: Efficient for small or nearly sorted lists. Time complexity: O(n^2).