Published: 13 Dec 2025 | Reading Time: 6 min read
This comprehensive guide provides:
Sorting is a technique that facilitates the handling of data by making it more manageable and easily searchable. One simple and efficient way, particularly for small or almost sorted data, is Insertion Sort. Due to its straightforward logic and gradual execution, it is a favorite in C programming.
Insertion Sort in C works by placing each element in its correct position within a growing sorted part of the list. While not ideal for large datasets, it's perfect for beginners learning sorting basics.
In this blog, you'll learn how Insertion Sort works in C, its algorithm, use cases, and how it compares to other sorting methods.
Sorting refers to the process of arranging a set of items in a certain sequence, most often from the smallest to the largest (ascending) or from the largest to the smallest (descending). It plays a major role in enhancing the efficiency of other operations, for instance, searching, as it makes data more accessible and easier to find.
Bubble Sort: One of the ways to sort data is by the use of a method called bubble sort. It is a simple method that, in a repetitive manner, compares and swaps adjacent elements if they are not in the correct order.
Selection Sort: This algorithm repeatedly finds the smallest (or largest) element and moves it to its correct position.
Merge Sort: This is a method that uses the divide and conquer principle, whereby the data is split down into smaller pieces, each piece is sorted separately, and finally, the pieces are combined in the right order.
Quick Sort: Another divide-and-conquer method that selects a "pivot" element and arranges the other elements around it before sorting them recursively.
Insertion Sort: This technique builds the sorted list one element at a time by placing each new element into its correct position within the already sorted section.
Insertion Sort in C is a specific sorting algorithm that organizes data step by step. When implementing insertion sort in a C program, it picks one element at a time from an unsorted list and places it in the correct position within a growing sorted section. This process continues until all elements are sorted.
In-Place Sorting: It does not require extra memory, as sorting happens within the original array.
Efficient for Nearly Sorted Data: Performs well when the list is already mostly sorted.
Stable Sorting: It keeps the relative order of equivalent items, so it is a beneficial feature for cases that require the preservation of the original order.
Time Complexity:
Insertion sort is a local, comparison-based sorting algorithm that builds the eventual sorted array one element at a time. The method first splits the array into two sub-lists: one sorted and one unsorted. Then, element by element, the algorithm takes the next element (the "key") from the unsorted sub-list and places it into the sorted sub-list at the proper position.
INSERTION_SORT(array):
for e from 1 to length(array) - 1:
key = array[e]
f = e - 1
while f >= 0 and array[f] > key:
array[f + 1] = array[f]
f = f - 1
array[f + 1] = key
Explanation:
RECURSIVE_INSERTION_SORT(array, n):
if n <= 1:
return
// Sort first n-1 elements
RECURSIVE_INSERTION_SORT(array, n - 1)
// Insert last element at its correct position
key = array[n - 1]
f = n - 2
while f >= 0 and array[f] > key:
array[f + 1] = array[f]
f = f - 1
array[f + 1] = key
Explanation:
A manual walkthrough helps clarify how insertion sort operates on an array, step by step. Let's simulate the process with a concrete example.
Insertion sort is a simple, in-place, stable algorithm that gradually builds a sorted array from the unsorted one, by way of one element at a time. Its logic is very similar to how you would sort playing cards in your hand.
Suppose we want to sort the array:
a = [9, 5, 1, 4, 3]
We will use the insertion sort algorithm to arrange the elements in ascending order.
| Step | Action | Resulting Array |
|---|---|---|
| 1 | Start | [9, 5, 1, 4, 3] |
| 2 | Insert 5 | [5, 9, 1, 4, 3] |
| 3 | Insert 1 | [1, 5, 9, 4, 3] |
| 4 | Insert 4 | [1, 4, 5, 9, 3] |
| 5 | Insert 3 | [1, 3, 4, 5, 9] |
Knowing how efficient insertion sort is can be a deciding factor in whether to use it or not. Below you can find its time and space complexity described for different situations:
When the array is already sorted, insertion sort only compares each element once without shifting.
Time Complexity: O(n)
This linear running time occurs because the inner loop never moves elements; no shifting is needed.
In the case where the input array is sorted in descending order, every new element will have to be compared and shifted all the way to the beginning of the already sorted part.
Time Complexity: O(n²)
The quadratic behavior is due to the fact that for each element, the algorithm makes the maximum possible number of comparisons and shifts.
With random data, the insertion sort will typically have to shift about half of the already sorted elements for each new element.
Time Complexity: O(n²)
The number of operations grows rapidly with larger arrays, making it inefficient for big datasets.
Insertion sort is an in-place algorithm, i.e. it only needs a constant number of extra memory space.
Space Complexity: O(1)
The only extra variable typically used is the key for comparison and insertion.
Remains O(1), as no additional data structures are used regardless of input arrangement.
| Scenario | Time Complexity | Space Complexity |
|---|---|---|
| Best Case (sorted) | O(n) | O(1) |
| Average Case | O(n²) | O(1) |
| Worst Case (reversed) | O(n²) | O(1) |
Insertion Sort is the one which goes on building the sorted array step by step by comparing the current element with the previous ones and then inserting the element into the correct place. The method is quite natural and is good enough when the dataset is small or almost sorted.
Below is a simple insertion sort C code implementation along with a detailed explanation:
#include <stdio.h>
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {7, 2, 5, 3, 1};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting: ");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
insertionSort(arr, size);
printf("\nAfter sorting: ");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
return 0;
}
Insertion Sort in C works by picking elements one by one and placing them in their correct position by shifting larger elements to the right. It starts from the second element and continues until the entire array is sorted. Insertion Sort C Code implements nested loops for comparing and inserting elements efficiently.
Before sorting: 7 2 5 3 1
After sorting: 1 2 3 5 7
The following code demonstrates how Insertion Sort can be implemented recursively using the C programming language.
#include <stdio.h>
void recursiveInsertionSort(int arr[], int size) {
if (size <= 1)
return;
recursiveInsertionSort(arr, size - 1);
int lastElement = arr[size - 1];
int j = size - 2;
while (j >= 0 && arr[j] > lastElement) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = lastElement;
}
int main() {
int arr[] = {8, 4, 2, 6, 1};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Before Sorting: ");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
recursiveInsertionSort(arr, size);
printf("\nAfter Sorting: ");
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
return 0;
}
This code indicates Insertion Sort in C using a recursive approach. Insertion Sort C Code works by first sorting a smaller part of the array and then placing the last element in its correct position by shifting larger elements forward.
Before Sorting: 8 4 2 6 1
After Sorting: 1 2 4 6 8
The insertion sort algorithm in C language benefits most from applications where its adaptability nature leads to faster running time, which is especially true for the best-case scenario or partially sorted data. Despite the fact that its average and worst cases are O(n²), as a result, it is still useful in various practical situations.
An insertion sort algorithm is close to perfect for situations when the data is almost pre-sorted.
Insertion sort beats more complex methods when working with tiny datasets.
It is a good solution when data is available one item at a time.
It is an algorithm that serves as the base concept of algorithm fundamentals and is thus most commonly referred to when teaching this field.
While inefficient for large arrays, insertion sort is practical for quick sorting of random order small lists.
By understanding these use cases, you can confidently choose insertion sort in C whenever you need a simple, stable, and efficient solution for small or nearly sorted datasets, real-time incremental sorting, or as a reliable component in hybrid sorting strategies.
Insertion Sort belongs to the family of O(n²) comparison-based sorting algorithms, but its adaptive behavior makes it faster than similar algorithms (like Bubble Sort) when the data is nearly sorted. Unlike divide-and-conquer algorithms such as Merge Sort and Quick Sort, insertion sort works in-place and is easier to implement, but performs poorly on large datasets. There exist a few advanced variants, like Binary Insertion Sort and Shell Sort, which reduce the number of comparisons or jumps, and they are extensively used in hybrid algorithms (Timsort, Introsort) as a result of its small subarray efficiency.
The table below gives a comparative overview of insertion sort and several common sorting algorithms, thereby emphasising differences in approach, complexity, adaptiveness, and typical use cases.
| Algorithm | Approach/Paradigm | Time Complexity (Best / Avg / Worst) | Space Complexity | Typical Use Cases / Notes |
|---|---|---|---|---|
| Insertion Sort | Incremental, In-place | O(n) / O(n²) / O(n²) | O(1) | Small or nearly sorted arrays; subroutine in hybrid sorts |
| Bubble Sort | In-place, Exchange | O(n) / O(n²) / O(n²) | O(1) | Educational purposes are rarely used in practice |
| Selection Sort | In-place, Selection | O(n²) / O(n²) / O(n²) | O(1) | Small datasets, when write operations are costly |
| Shell Sort | In-place, Gap Insertion | O(n log n) / O(n^1.5) / O(n²) | O(1) | Improved insertion sort for larger arrays |
| Merge Sort | Divide-and-Conquer | O(n log n) / O(n log n) / O(n log n) | O(n) | Large datasets, stable sort needed |
| Quick Sort | Divide-and-Conquer | O(n log n) / O(n log n) / O(n²) | O(log n) | General-purpose, fast for large datasets |
| Heap Sort | Heap-based, In-place | O(n log n) / O(n log n) / O(n log n) | O(1) | Large datasets, when constant space is needed |
| Binary Insertion Sort | Incremental, Binary Search | O(n log n) / O(n²) / O(n²) | O(1) | Fewer comparisons than regular insertion sort, but same number of shifts |
| Hybrid Approaches (e.g., TimSort, IntroSort) | Adaptive/Hybrid | O(n) / O(n log n) / O(n log n) | O(n) | Real-world libraries, switch to insertion sort for small subarrays |
Insertion sort is simple, stable, and adaptive, making it ideal for small or nearly sorted data. It is often used as a subroutine in hybrid algorithms like TimSort and IntroSort.
Bubble sort is also stable and adaptive, but generally less efficient than insertion sort.
Selection sort is not stable and not adaptive, but minimizes the number of writes, making it useful when write operations are costly.
Shell sort makes insertion sort more efficient by allowing the exchange of elements that are far apart, thus decreasing the total number of shifts for larger arrays.
Merge sort and quick sort are significantly faster for large datasets because of their O(n log n) average time complexity, but belong to different paradigms (divide-and-conquer).
Heap sort gives O(n log n) performance and is in-place; however, it is not a stable sort.
Binary insertion sort employs binary search to locate the insertion point, thus reducing comparisons; however, it still necessitates O(n²) shifts.
Hybrid methods bring into play insertion sort for small subarrays, thus benefiting from its efficiency on small data while gaining the speed of faster algorithms on large data.
Insertion sort comes with a mix of strengths and limitations, making it highly effective in some scenarios while inefficient in others, especially as data size grows.
Easy to Understand and Implement: Insertion Sort is easy for beginners to understand, which makes it a perfect pick for those who are new to sorting algorithms. The idea of one by one, taking an element and putting it in the right place, is quite simple.
Memory Efficient: The method is a non-space-demanding one as it sorts the given array without any additional storage. The amount of additional memory utilized is only constant (O(1)).
Works Well for Nearly Sorted Data: If the input data is already mostly sorted, Insertion Sort performs significantly faster, making fewer comparisons and swaps compared to other algorithms. This adaptive nature allows it to be more efficient in such cases.
Stable Sorting Algorithm: In the final sorted list, the algorithm keeps the initial order of equal entries. The feature can be helpful in applications where the order of duplicates needs to be maintained.
Slow for Large Datasets: Insertion Sort has a time complexity of O(n²) for its worst-case and average-case scenarios, implying that the algorithm is very slow for large arrays. More precisely, the growth of the number of comparisons and swaps with the size of the dataset is exponential.
Not Suitable for Parallel Processing: Unlike some sorting algorithms that can divide the workload across multiple processors, Insertion Sort works in a step-by-step manner.
High Number of Data Movements: Every time an element is inserted into the sorted part of the array, it may require shifting multiple elements. This leads to increased memory operations, especially in large datasets.
Inefficient for Randomly Ordered Data: Insertion Sort works best when the data is already sorted or nearly sorted. However, when the input data is in random or reverse order, it performs very poorly.
Not a Stable Choice for Performance-Critical Applications: The reason for Insertion Sort to be rarely found in such applications as where speed and performance are critical is its slow performance on large or unsorted data. In these cases, other algorithms such as Merge Sort or Quick Sort are chosen.
Insertion Sort in C is an excellent example that visually and logically walks through the principles of sorting algorithms. It performs fine on small or almost sorted datasets, and since it is simple to implement, it is perfect for those who are learning. Though it is less efficient than a fast algorithm like Quicksort or Mergesort when it comes to large data, it is still a good stepping stone for understanding the essential concepts of sorting.
Insertion Sort in C is adaptive and stable, making it exceptionally fast on partially sorted data despite its O(n²) worst case.
It is the go-to method for small arrays or subarrays, which is why modern algorithms like Timsort and Introsort switch to it internally.
Shifting, not swapping, defines its behavior, which reduces unnecessary write operations and preserves the ordering of equal elements.
The algorithm performance depends on the input heavily: O(n) best case, but O(n²) for random or reverse-sorted data.
If you care about code clarity, simplicity, or incremental data processing, then go ahead with insertion sort. On the other hand, if you have a large dataset or highly unsorted inputs, better not to use it.
Insertion sorting is a method for sorting numbers by arranging them one at a time. It picks an item from the unsorted section and places it where it belongs in the sorted part, shifting larger numbers to the right when needed.
Yes, the insertion sort is stable. This means if two elements have the same value, they will stay in the same order as they were in the original list.
In the worst and average cases, insertion sort takes O(n²) time, which makes it slow for big lists. However, if the data is almost sorted, it can run in O(n) time.
In C, insertion sort is generally implemented with a loop. Every number is checked against the ones before it and, if necessary, it is placed in the correct position. This means that nested loops are used to compare and shift elements.
Simple to understand and code, uses very little extra memory (O(1)), and works well on small or nearly sorted lists.
It is best for small datasets or lists that are already mostly sorted. It's also useful when new data keeps coming in and needs quick sorting.
Yes, it can be written in a recursive way by sorting part of the list first and then inserting the next element into the right spot. This follows the same logic as the regular version but uses function calls instead of loops.
Source: NxtWave - https://www.ccbp.in/blog/articles/insertion-sort-in-c