# Insertion Sort

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(n2).

### 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);
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

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

### Bucket Sort

Here, We will discuss about Bucket Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. …

### Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Quick Sort? Quick …

### Sorting Algorithms

Here, We will learn about sorting algorithms, why is sorting necessary, classification and complexity of sorting, types of sort. What is Sorting? Sorting refers to arranging data …

### Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Merge Sort? Merge …

### Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Counting …

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. 