Here, We will learn about insertion sort in C, their algorithm, implementation code in C, time and space complexity and advantages..

**What is Insertion sort?**

**Insertion Sort** is a simple and efficient comparison sort. It works similarly as we sort cards in our hand in a card game.

The algorithm based on the idea that places an unsorted element at its suitable place in each iteration.

This sort algorithm with expensive runtime with O(n^{2}).

**Insertion Sort Algorithm**

Every repetition of this sort removes an element from the input data and inserts it into the correct position in the already-sorted list until no input elements remain.

**Implementation of Insertion Sort**

**Program Code in C :-**

```
#include<stdio.h>
//function to print array
void printarray(int arr[], int n)
{
for(int i=0; i<n; i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
void insertionSort(int arr[], int n)
{
for(int i=0; i<n; i++)
{
int k = arr[i];
int j = i-1;
//compare key with each element on the left of it until an element
//smaller than it is found.
while(k < arr[j] && j >=0)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = k;
}
}
//Driver code
int main()
{
int data[] = {4, 75, 74, 2, 54};
int n = sizeof(data) / sizeof(data[0]);
insertionSort(data, n);
printf("Sorted array : ");
printarray(data, n);
}
```

Code language: C++ (cpp)

**Output :-**

`Sorted array : 2 4 54 74 75`

Code language: PHP (php)

**Time and Space Complexity of Insertion Sort**

Time Complexity | |

Worst Case | O(n^{2}) |

Best Case | O(n) |

Average Case | O(n^{2}) |

Space Complexity | |

Worst Case | O(n total^{2})O(1) auxiliary |

**Advantages of Insertion Sort**

- Simple implementation.
- Efficient for small data.
- Stable: Maintains relative order of input data if the keys are the same.
- In-place requires only a constant amount O(1) of additional memory space.

### Other Sorting Algorithms:-

### Related:

#### Radix Sort

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C,…

#### Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time…

#### Heap Sort

Here, We will discuss about Heap Sort in C, their algorithm, implementation code in C,…

#### Bucket Sort

Here, We will discuss about Bucket Sort in C, their algorithm, implementation code in C,…

#### Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C,…

#### Shell Sort

Here, We will discuss about Shell Sort in C, their algorithm, implementation code in C,…

*Want to Contribute*:-

If you like “**To The Innovation**” and want to contribute, you can mail your articles to ðŸ“§ **[email protected]**. See your articles on the main page and help other coders.ðŸ˜Ž