Insertion Sort in C: Algorithm, Code, and Step-by-Step Guide

Insertion sort in C is one of the simplest sorting algorithms you will learn as a programmer. It works the way you naturally sort playing cards in your hand: pick one card, find its right position among the already-sorted cards, and slide it in. Simple, intuitive, and a great starting point for understanding how sorting works under the hood.

In this blog, you will learn what insertion sort is, how the algorithm works, how to write the insertion sort program in C with a full working code, trace through a dry run, understand its time and space complexity, and see where it actually makes sense to use it. Whether you are just starting out or brushing up for interviews, this blog covers everything.

Ready to go beyond algorithms and start building real-world AI solutions? Explore upGrad’s Artificial Intelligence Courses to learn machine learning, generative AI, and cutting-edge technologies through hands-on projects and practical applications.

What Is Insertion Sort in C?

Insertion sort is a comparison-based sorting algorithm. It builds a sorted array one element at a time by picking each element and inserting it into its correct position in the already-sorted portion.

Think of it this way: you have a list of numbers. You start with the first element (it is already "sorted" on its own). Then you take the second element and compare it with the first. If it is smaller, you move it before the first. You continue doing this for each element until the entire array is sorted.

Key Characteristics

• In-place algorithm: It does not need extra memory for a separate array.
• Stable sort: Equal elements maintain their original order.
• Adaptive: If the array is already sorted or nearly sorted, it runs much faster.
• Simple to implement: Very few lines of code.

The insertion sort algorithm in C is especially useful when you are working with small datasets or nearly sorted data. For large, random datasets, faster algorithms like merge sort or quicksort are better choices.

Also Read: Data Structures and Algorithms (DSA)

Insertion Sort Algorithm in C: How It Works

Before writing any code, understand the logic step by step.

The algorithm:

1. Start from the second element (index 1). Treat the first element as already sorted.
2. Store the current element in a temporary variable (called key).
3. Compare key with elements to its left.
4. Shift every element that is greater than key one position to the right.
5. Insert key into the correct position.
6. Repeat for all remaining elements.

Dry Run Example

Let us sort this array: {5, 3, 8, 1, 4}

• Pass 1 (i = 1, key = 3): Compare 3 with 5. Since 5 > 3, shift 5 right. Insert 3 at index 0. Array: {3, 5, 8, 1, 4}
• Pass 2 (i = 2, key = 8): Compare 8 with 5. Since 5 < 8, no shift needed. Array stays: {3, 5, 8, 1, 4}
• Pass 3 (i = 3, key = 1): Compare 1 with 8, then 5, then 3. All are greater, so shift all three right. Insert 1 at index 0. Array: {1, 3, 5, 8, 4}
• Pass 4 (i = 4, key = 4): Compare 4 with 8, then 5. Both greater, shift right. Compare 4 with 3. 3 < 4, so stop. Insert 4 at index 2. Array: {1, 3, 4, 5, 8}

Sorted array: {1, 3, 4, 5, 8}

Each pass grows the sorted portion by one element. By the last pass, the entire array is sorted.

Also Read: Insertion Sort Algorithm in Data Structures

Insertion Sort Program in C: Full Code With Explanation

Here is the complete insertion sort code in C. It is clean, well-commented, and beginner-friendly.

#include <stdio.h>

// Function to perform insertion sort
void insertionSort(int arr[], int n) {
   int i, key, j;

   for (i = 1; i < n; i++) {
       key = arr[i];   // Element to be placed correctly
       j = i - 1;

       // Shift elements greater than key one position to the right
       while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
       }

       // Place key in its correct position
       arr[j + 1] = key;
   }
}

// Function to print array
void printArray(int arr[], int n) {
   for (int i = 0; i < n; i++) {
       printf("%d ", arr[i]);
   }
   printf("\n");
}

// Main function
int main() {
   int arr[] = {5, 3, 8, 1, 4};
   int n = sizeof(arr) / sizeof(arr[0]);

   printf("Original array: ");
   printArray(arr, n);

   insertionSort(arr, n);

   printf("Sorted array:  ");
   printArray(arr, n);

   return 0;
}

Output:

Original array: 5 3 8 1 4
Sorted array:   1 3 4 5 8

Breaking Down the Code

• key = arr[i] This stores the current element you want to insert into the correct position.
• while (j >= 0 && arr[j] > key) This loop moves backward through the sorted portion. As long as elements are greater than key, they shift right by one position.
• arr[j + 1] = key Once the correct position is found, key is inserted there.

The outer for loop runs n-1 times. The inner while loop runs a variable number of times depending on how many elements need shifting.

Also Read: Understanding While Loop in Python with Examples

Taking User Input

If you want to sort a user-defined array, here is the modified insertion sort program in C:

#include <stdio.h>

void insertionSort(int arr[], int n) {
   for (int i = 1; i < n; i++) {
       int key = arr[i];
       int j = i - 1;
       while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
       }
       arr[j + 1] = key;
   }
}

int main() {
   int n;
   printf("Enter number of elements: ");
   scanf("%d", &n);

   int arr[n];
   printf("Enter %d elements:\n", n);
   for (int i = 0; i < n; i++) {
       scanf("%d", &arr[i]);
   }

   insertionSort(arr, n);

   printf("Sorted array: ");
   for (int i = 0; i < n; i++) {
       printf("%d ", arr[i]);
   }
   printf("\n");

   return 0;
}

This version reads input at runtime, making it flexible for any dataset.

Also Read: Insertion Sort in Java: Explained with Examples

Time and Space Complexity of Insertion Sort in C

Understanding complexity is essential for interviews and for choosing the right algorithm in real-world situations.

Time Complexity

Case	Condition	Complexity
Best Case	Array is already sorted	O(n)
Average Case	Elements are in random order	O(n²)
Worst Case	Array is sorted in reverse order	O(n²)

Why O(n) in the best case? When the array is already sorted, the inner while loop never executes. The outer loop runs n-1 times, so total comparisons are just n-1. That is linear time.

Why O(n²) in the worst case? When the array is reverse sorted, every element needs to be shifted past all previously sorted elements. For n elements, total shifts are 1 + 2 + 3 + ... + (n-1) = n(n-1)/2, which is O(n²).

Space Complexity

Insertion sort in C uses O(1) auxiliary space. It works directly on the input array. No extra array is created. Only a single key variable is needed.

Comparison With Other Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No

Insertion sort outperforms even merge sort for very small arrays (fewer than 10-15 elements) due to low overhead. Many standard library sort implementations switch to insertion sort for small subarrays for this exact reason.

When to Use Insertion Sort in C (and When Not To)

Choosing the right algorithm matters. Here is when insertion sort is a good pick:

Use Insertion Sort When:

• The dataset is small. For arrays with fewer than 20-30 elements, insertion sort performs well.
• The data is nearly sorted. If only a few elements are out of place, it is extremely fast (approaching O(n)).
• You need a stable sort with no extra memory. Insertion sort is in-place and stable.
• Online sorting is needed. You can sort data as it arrives, one element at a time, without waiting for the full dataset.
• Simplicity of code matters. In embedded systems or competitive programming with small inputs, insertion sort is quick to write and debug.

Avoid Insertion Sort When:

• The dataset is large (thousands or millions of elements).
• Data is in completely random order.
• Performance is a top priority and the input size is unpredictable.

Practical Uses in Real Life

• Sorting a hand of cards
• Sorting a small list of student scores
• Implementing hybrid sorting algorithms (Timsort uses insertion sort for small chunks)
• Building simple sorting logic in microcontrollers with limited memory

Also Read: Time and Space Complexity in Machine Learning Algorithms Explained

Variations of Insertion Sort in C

Once you understand the basic version, you can explore these variations:

Recursive Insertion Sort

Instead of using loops, you can write insertion sort recursively.

void recursiveInsertionSort(int arr[], int n) {
   if (n <= 1)
       return;

   // Sort first n-1 elements
   recursiveInsertionSort(arr, n - 1);

   // Insert last element at its correct position
   int last = arr[n - 1];
   int j = n - 2;

   while (j >= 0 && arr[j] > last) {
       arr[j + 1] = arr[j];
       j--;
   }
   arr[j + 1] = last;
}

The logic is the same. The difference is that each recursive call sorts a smaller portion, and then the last element is inserted.

Binary Insertion Sort

Instead of using linear search to find the correct position, you use binary search. This reduces the number of comparisons from O(n²) to O(n log n), but the number of shifts is still O(n²). So the overall time complexity remains O(n²) for shifts, but comparisons improve.

int binarySearch(int arr[], int item, int low, int high) {
   while (low <= high) {
       int mid = (low + high) / 2;
       if (item == arr[mid])
            return mid + 1;
       else if (item > arr[mid])
            low = mid + 1;
       else
            high = mid - 1;
   }
   return low;
}

void binaryInsertionSort(int arr[], int n) {
   for (int i = 1; i < n; i++) {
       int key = arr[i];
       int pos = binarySearch(arr, key, 0, i - 1);

       int j = i - 1;
       while (j >= pos) {
            arr[j + 1] = arr[j];
            j--;
       }
       arr[j + 1] = key;
   }
}

Binary insertion sort is useful when comparisons are expensive (for example, comparing strings or complex objects).

Conclusion

Insertion sort in C is a clean, simple algorithm that every programmer should know. It is not the fastest for large datasets, but it shines when dealing with small arrays or nearly sorted data. The insertion sort code in C is easy to write, easy to debug, and easy to explain, which makes it a go-to choice for learning the fundamentals of sorting.

If you want to go deeper into data structures and algorithms, exploring more complex algorithms like merge sort, quicksort, and heap sort will build a strong foundation for coding interviews and real-world software development.

Want personalized guidance on AI and upskilling? Speak with an expert for a free 1:1 counselling session today.