---
description: >-
  This sorting algorithm works by repeatedly inserting elements into their
  correct position in an array.
---

# 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.&#x20;

**`Question statement:`**[ ](https://www.codingninjas.com/studio/problems/insertion-sort_3155179)[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](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="https://3848643327-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F07O01HTuDHqLK3IxhYPe%2Fuploads%2FuZhNRUWtsjHKoEEqxCIr%2Fimage.png?alt=media&#x26;token=0b656733-d246-45e6-a165-339b4f01e3ca" 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)
