---
# System prepended metadata

title: Insertion Sort Program in C - Scaler Topics

---

---
canonical_url: https://www.scaler.com/topics/insertion-sort-program-in-c/
title: Insertion Sort Program in C - Scaler Topics
description: Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part.
category: C
author: Niyati Thakkar
---

:::section{.abstract}


`Insertion Sort` is a simple algorithm for sorting arrays. It divides the array into two parts: sorted and unsorted. Starting with the second element, each item is picked from the unsorted section and placed in its correct position in the sorted section. This is achieved by comparing the current element with the elements in the sorted section and shifting them if necessary to make space for the current element. The process continues until all elements are sorted. Unlike two separate arrays, this method sorts the array in place, minimizing memory usage. 
`Insertion Sort` is efficient for small arrays or nearly sorted arrays but becomes inefficient for larger datasets due to its time complexity of O(n^2).
:::

:::section{.main}
## Characteristics of Insertion Sort
* It is one of the simplest algorithms to sort an array. It is easy to understand and implement.
* It is efficient only for a small number of data values.
* Insertion sort is appropriate if the data is `partially sorted`, i.e. it is adaptive in nature. 
* It follows an `incremental approach`, i.e. the number of elements in the sorted section of the array is increased one by one. 
* It is a stable and in-place sorting algorithm.

:::

:::section{.main}
## Working of Insertion Sort Algorithm
Let us take an example of the array as follows:
{45, 33, 2, 60, 71, 68}
Initially, the array is as follows:

![array-initial-state](https://www.scaler.com/topics/images/array-initial-state.webp)

**First iteration:**
* Initially, the first element is sorted, and i points to the second element, i.e., 33. Now, j points to the 45. After running the while loop, j = -1, cur = 33, and the array is - 

![first-iteration-of-array](https://www.scaler.com/topics/images/first-iteration-of-array.webp)

**While Loop:**

![while-loop-on-arary](https://www.scaler.com/topics/images/while-loop-on-arary.webp)

* At the end of for loops iteration, we place cur at its position, i.e. j+1 = 0, and the array becomes

![array-after-for-loop](https://www.scaler.com/topics/images/array-after-for-loop.webp)



**Second iteration:**

* Now I point to 2, and j points to 33. After execution of the while loop

![second-iteration-of-array](https://www.scaler.com/topics/images/second-iteration-of-array.webp)

**While Loop:**

* arr[j] = cur

![while-loop-on-second-iteration](https://www.scaler.com/topics/images/while-loop-on-second-iteration.webp)

![while-loop-on-second-iteration2](https://www.scaler.com/topics/images/while-loop-on-second-iteration2.webp)

At the end of the second iteration, the array is as follows:

![array-after-second-iteration](https://www.scaler.com/topics/images/array-after-second-iteration.webp)

**Third iteration:**
At the beginning of the third iteration,

![array-beginning-of-third-iteration](https://www.scaler.com/topics/images/array-beginning-of-third-iteration.webp)

* cur = 60, j points to 45, and 60 is greater than 45; thus, we are not required to modify anything in this iteration.

![third-iteration](https://www.scaler.com/topics/images/third-iteration.webp)


**Fourth iteration:**
* At the beginning of the fourth iteration,

![array-beginning-of-fourth-iteration](https://www.scaler.com/topics/images/array-beginning-of-fourth-iteration.webp)

* Now, cur = 71, and j is 60, which is less than 71. Thus, again, the array is sorted so far. 

![array-after-fourth-iteration](https://www.scaler.com/topics/images/array-after-fourth-iteration.webp)



**Fifth iteration:**

* Array at the beginning of the fifth iteration:

![array-beginning-of-fifth-iteration](https://www.scaler.com/topics/images/array-beginning-of-fifth-iteration.webp)

* Lastly, i points to 29 i.e. cur = 29 and j = 4 i.e. 71. Variation during the while loop in the array is as follows:

![fourth-iteration-of-array](https://www.scaler.com/topics/images/fourth-iteration-of-array.webp)

![fourth-iteration-of-array2](https://www.scaler.com/topics/images/fourth-iteration-of-array2.webp)

![fourth-iteration-of-array3](https://www.scaler.com/topics/images/fourth-iteration-of-array3.webp)

![fourth-iteration-of-array4](https://www.scaler.com/topics/images/fourth-iteration-of-array4.webp)


* Now, cur must be placed at position 4. The resultant array is as follows:
 
![resultant-array](https://www.scaler.com/topics/images/resultant-array.webp)

The sorted array after execution of the insertion sort is as follows:

![sorted-array-after-execution-of-insertion-sort](https://www.scaler.com/topics/images/sorted-array-after-execution-of-insertion-sort.webp)

:::

:::section{.main}

## Insertion Sort Algorithm

The steps to implement the insertion sort algorithm are described below:

1. We assume that the array is empty and that inserting one element into it will not affect the sorting order of the array. Thus, the first element is already sorted.
2. We run a loop from the second element to the last element in the array. Each iteration compares the current element with the previous elements, and its correct position is searched. 
3. If the current element is greater than or equal to the previous element, then we move towards the next iteration. If the current element is smaller than the previous elements, all the elements greater than the current are shifted one position to the right, and the current element is placed at its correct position.
4. Step 3 is repeated for each element in the array.

The array is sorted now. Let us look at its pseudo code for a better understanding:

```c
arr = {6, 7, 3, 9, 1}
n = 5
void insertionSort(){
    cur = 0;
    j = 0;
    
    for(int i = 1; i < n; i++){
        cur = arr[i];
        j = i-1;
        
        // finding the right position for the current and shifting one position to the right
        while(j >= 0 && cur<arr[j]){
            arr[j+1] = arr[j];
            j--;
        }
        
        // placing current to its correct position
        arr[j+1] = cur;
    }
}
```
In the above code, the outer for loop visits each array element. The inner while loop moves all the elements greater than cur to the one position right. Finally, the cur is placed in the right position.

![insertion-sort-examples](https://www.scaler.com/topics/images/insertion-sort-examples.webp)

:::

:::section{.main}
## Implementation 

Here, We are using an outer loop to visit all the elements of the loop and an inner while loop to search for the position of the current element and shift greater elements to one step right. 

```c
#include <stdio.h>

void insertionSort(int arr[], int n){
    // if the array is empty or has only one element
    if(n==0 || n==1) return;
    int cur = 0, j = 0;
    
    // assuming that first elements in the array is sorted therefore, i=1
    for(int i = 1; i < n; i++){
        // storing current element
        cur = arr[i];
        j = i-1;
        // finding right position for cur element and 
        // sawpping all the greater elements to the right side
        while(j >= 0 && arr[j] > cur){
            arr[j+1] = arr[j];
            j--;
        }
        
        // placing current at its position
        arr[j+1] = cur;
        
    }
    // array is sorted now
}

// function to print array elements
void printArr(int arr[], int n){  
    int i;  
    for (i = 0; i < n; i++)  
        printf("%d ", arr[i]);  
}  
  
int main(){
    // array to be sorted
    int arr[] = { 78, 90, 12, 42, 30, 65, 92 };  
    // length of the array
    int n = sizeof(arr) / sizeof(arr[0]);  
    
    // printing array before sorting
    printf("Array elements initially - \n");  
    printArr(arr, n); 
    
    // soring array
    insertionSort(arr, n);
    
    // printing array after sorting
    printf("\nArray elements after applying insertion sort - \n");    
    printArr(arr, n); 

    return 0;
}
```
**Output:**
```plaintext
Array elements initially - 
78 90 12 42 30 65 92 
Array elements after applying insertion sort - 
12 30 42 65 78 90 92 
```

### Time Complexity

* **Best Case -** `O(n)`. 
* **Worst Case -**  **$O(n^2)$** 
* **Average Case -** **$O(n^2)$** 

### Space Complexity  

The Space complexity of the insertion sort algorithm in all the cases is `O(1)`.

:::
:::section{.main}
## Boundary Cases of Insertion Sort in C

Boundary cases in algorithms represent scenarios where the algorithm performs at its best or worst. In the case of Insertion Sort, the best scenario arises when the input array is already sorted, while the worst scenario occurs when the array is sorted in reverse order.

In the best-case scenario, with a sorted input array, each new element in the unsorted section must only be compared once, resulting in a single pass through the array. This leads to an O(n) time complexity, where n is the array size.

Conversely, in the worst-case scenario where the array is sorted in reverse order, every new element in the unsorted section must be compared with all elements in the sorted section, necessitating the shifting of elements and resulting in a time complexity of O(n^2).

Thus, the efficiency of Insertion Sort significantly varies based on the input scenario. Understanding these boundary cases is crucial for evaluating the algorithm's performance accurately, highlighting its sensitivity to the initial order of elements in the array.
:::
:::section{.main}

## Algorithmic Paradigm of Insertion Sort in C 
The insertion sort algorithm employs several algorithmic paradigms to sort arrays efficiently. 
* Firstly, it adopts an iterative approach, utilizing loops to traverse the array and insert each element into its appropriate position within the sorted section. 
* it applies the divide and conquer strategy by segmenting the array into sorted and unsorted portions, iteratively incorporating elements from the latter into the former until the entire array is sorted.
* Insertion sort operates in-place, necessitating no extra storage beyond the original array, which enhances its memory efficiency.
* It upholds stability, ensuring that the relative order of equivalent elements remains unchanged in the sorted output. 
* Despite its effectiveness for minor to moderate arrays, its O(n^2) time complexity renders it less suitable for larger datasets. 


These combined strategies enable insertion sort to organize arrays proficiently, balancing performance considerations with memory constraints and preserving the order of identical elements.

:::
:::section{.main}

## FAQs 

*  **Is Insertion Sort a Stable Algorithm?**
 Yes, Insertion Sort is a stable algorithm.

*  **Is Insertion Sort an in-place algorithm?**
Yes, Insertion Sort is an in-place algorithm.

*  **What is Binary Insertion Sort?**
Binary Insertion Sort is a variation of Insertion Sort that uses binary search to find the correct position to insert each element, improving its efficiency.

*  **How to Implement Insertion Sort for Linked Lists?**

   Implementing Insertion Sort for Linked Lists involves iteratively removing nodes from the input list and inserting them into their correct position in a new sorted list.

*  **When in Insertion Sort Algorithm Used?**
Insertion Sort is commonly used when dealing with small to moderate-sized arrays or when the array is nearly sorted.


:::

:::section{.summary}
## Conclusion
* Insertion sort algorithm is one of the simplest ways to sort the array. 
* It is easy to implement and for and/or while loops can be used for implementation.
* Its average case time complexity is **$O(n^2)$** and space complexity is `O(1)`.
* It is suitable for a small and partially sorted data set.

:::