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

# Insertion Sort

**Insertion sort** is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part. 

**`Question statement:`**[ ](https://www.codingninjas.com/studio/problems/insertion-sort_3155179)<https://www.codingninjas.com/studio/problems/insertion-sort_3155179>

**`Notes:`**[ ](https://drive.google.com/file/d/10zLQIWEn55nwhFOrHybqnxexf96AX1LE/view)<https://drive.google.com/file/d/10zLQIWEn55nwhFOrHybqnxexf96AX1LE/view>

```cpp
void InsertionSort(int n, vector<int> &arr){
    for(int i = 1; i < n; i++){
        // for rounds 1 to n-1
        //Here we assume 0 index value as sorted
        
        int temp = arr[i];
        int j = i-1;

        for(; j >= 0; j--){
            if(arr[j] > temp) // {1, 4, 2, 3} 
                // Shifting j index value forward by 1
                arr[j+1] = arr[j]; // now array becomes {1, 4, 4, 3} 2 is already stored in temp 
            else 
                break;
        }
        swap(arr[j+1], temp);
    }
}
```

<figure><img src="/files/Z5PS296OE6ArGx8GI0KE" alt=""><figcaption></figcaption></figure>

**`Space Complexity:`** constant O(1)

**`Time complexity:`**&#x4F;(n^2)

<pre class="language-cpp"><code class="lang-cpp"><strong>// 1st round - 1 Comp
</strong></code></pre>

```cpp
// 2nd round - 2 Comp...
```

```cpp
// (nth - 1) Round - (n-1) comp 
```

**`Best case:`** Already Sorted  = {1, 2, 3, 4,}  T.C = O(n)

```cpp
// total comparisons (n-1) 
```

**`Worst Case:`**&#x52;eversed Array = {4, 3, 2, 1}  T.C = O(n^2)