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

Have you ever seen students lining up by height at school? One by one, each student finds their correct place in the line. What if we could teach a computer to do the same with the numbers? This is where the insertion sort algorithm is used. It picks one element at a time and places it in the correct place. But is it fast enough for large lists? Or only good for small ones? In this article, we will learn what insertion sort in C is, with its advantages and disadvantages, in detail.

Table of Contents:

• What is Insertion Sort?
• Algorithm of Insertion Sort in C
• How Does Insertion Sort Work in C?
• C Program of Insertion Sort
  • Iterative Insertion Sort in C
  • Recursive Insertion Sort in C
  • Insertion Sort on Linked List
• Variants of Insertion Sort in C
• Time and Space Complexity of Insertion Sort in C
• Advantages of Insertion Sort in C
• Disadvantages of Insertion Sort in C
• Conclusion

What is Insertion Sort?

Insertion Sort is a comparison-based sorting algorithm used to arrange a list or array of elements in a specific order, usually ascending or descending. It inserts each new element into its correct position in the already sorted part of the array. For example, just like arranging books on a shelf by size, each new book is picked up and placed in its correct position among the already sorted books. Insertion Sort picks one element at a time and inserts it into its proper place in the sorted section of the array.

Why Is It Called “Insertion” Sort?

The sorting technique is called Insertion Sort because it makes the final sorted list one item at a time by inserting each element into its correct position. It divides the array into two parts:

• Sorted part: It stores the first element.
• Unsorted part: All the remaining elements are present in this part.

We have to go through the unsorted part of the array, one element at a time. For each element, we can compare it with the elements in the sorted part. Then, the larger elements in the sorted part are shifted one position to the right, and the current element is inserted into its correct place. This process is repeated until the entire array is sorted.

Unlock Your Future in C

Start Your C Journey for Free Today

Explore Program

Algorithm of Insertion Sort in C

1. Start from the second element, because the first element in insertion sort is considered sorted.
2. Store the current element in a temporary variable, temp.
3. Compare the temp with the elements present to its left.
4. Keep shifting the elements greater than the temp to the right position.
5. Insert the temp at its correct position, i.e., where it is not less than the previous element.
6. Repeat this process for all the elements in the array.

Pseudocode of Insertion Sort

for i 1 to n-1:
    temp= arr[i]
    j = i - 1
    while j >= 0 and arr[j] > temp:
        arr[j + 1] = arr[j] // Shift the current element to the right
        j = j - 1
    arr[j + 1] = temp; // Insert temp in its correct position

• arr[ ] is an array
• n is the length of the array
• i is the current element’s index in the unsorted part
• temp is the temporary variable
• j is a pointer used to compare temp with the elements to its left.

How Does Insertion Sort Work in C?

Let us sort the array: arr = [6, 3, 5, 2, 4]. The array has n = 5 elements, and the sorting starts from index i = 1.

Step 1: First Comparison

In this step, we will discuss the first step of insertion sort by comparing the first 2 elements in the array. We assume that the first element of the array is already sorted, and we will sort the remaining elements.

• The temp = arr[1] = 3, then j = i – 1 = 0
• First, compare elements 3 and 6, present at the indices 0 and 1. Since arr[j](6) is greater than temp(3), hence, shift 6 to the right, arr = [6, 6, 5, 2, 4], and j = -1, this loop will stop.
• Now, insert element 3 at j = 0. Then the array will become arr = [3, 6, 5, 2, 4].

Step 2: Insertion in the Middle

In the previous step, we sorted the first 2 elements of the array, and now we are going to sort the first three elements.

• The variable, temp= arr[2] = 5, then j = 1.
• Compare elements 5 and 6, present at the indices 1 and 2. Since arr[1](6) is greater than temp(5), hence, shift 6 to the right, arr = [3, 6, 6, 2, 4], and j = 0.
• Compare elements 5 and 3. Since arr[0](3) is smaller than temp, we stop shifting and insert 5 at j + 1 = 1, i.e., arr = [3, 5, 6, 2, 4].

Step 3: Shift Multiple Elements

Now, in step 3, we will see how to sort the remaining elements in the array.

• The variable, temp= arr[3] = 2, then j = 2.
• Compare elements 2 and 6 present at the indices 2 and 3. Since arr[2](6)is greater than temp(2), then shift 6 to the right (assign arr[3] = arr[2]), resulting in arr = [3, 5, 6, 6, 4].
• Now, j = 1, compare elements 2 and 5. Since arr[1](5) is greater than temp(2), then shift 5 to the right (assign arr[2] = arr[1]), resulting in arr = [3, 5, 5, 6, 4].
• Now, j = 0, compare elements 2 and 3. Since arr[0](3) is greater than temp(2), then shift 3 to the right, arr = [3, 3, 5, 6, 4].
• Now, insert element 2 at j = 0. Then the array will become arr = [2, 3, 5, 6, 4]

Step 4: Final Adjustment

This is the final step of the insertion sort because only 2 elements are to be sorted. In this step, we will discuss how the elements will be compared.

• The variable, temp= arr[4] = 4, then j = 3.
• Compare elements 4 and 6 present at the indices 3 and 4. Since arr[3](6) is greater than temp(4), hence, shift 6 to the right (assign arr[4] = arr[3]), resulting in arr = [2, 3, 5, 6, 6].
• Now, j = 2, compare elements 4 and 5. Since arr[2](5) is greater than temp(4), hence, shift 5 to the right (assign arr[3] = arr[2]), resulting in arr = [2, 3, 5, 5, 6].
• Since arr[1](3) is smaller than temp (4), stop shifting. Insert temp at index 2: arr = [2, 3, 4, 5, 6].

Final Sorted Array = [2, 3, 4, 5, 6]

C Program of Insertion Sort

Insertion Sort in C can be implemented in multiple ways. Some of them are discussed below.

1. Iterative Insertion Sort in C

In this approach, we will learn how to sort an array by using a for loop. The iterative version of Insertion Sort uses a for loop to go through each element and insert it into its correct position in the already sorted part of the array. The while loop is used to check the condition of the variable j, which is j >= 0 && arr[j] > temp

Output:

Explanation: The above C program sorts an array using the for loop iterative approach. It starts from the second element and then compares every element with the elements that are present on its left. If any element greater than the temp element is found, the element is shifted to the right, and then the temp is inserted into its right position in the sorted section.

2. Recursive Insertion Sort in C

Recursive Insertion Sort uses recursion to sort the array, but it follows the same basic logic as the iterative version of the insertion sort does, and the sorting is done by breaking the problem into smaller subproblems.

Output:

Explanation: The above C program uses recursion to sort an array. The function recursiveInsertionSort(int arr[], int n) sorts the first n elements of the array by using insertion sort. It first recursively sorts the first n-1 elements, then it inserts the last element (key) into its correct position in the sorted subarray.

3. Insertion Sort on Linked List

Insertion Sort can be applied to linked lists, as they do not require the shifting of elements, and only the pointer of the element is changed. This makes insertion sort an efficient sorting technique for both singly and doubly linked lists.

Output:

Explanation: The above C program sorts a linked list using insertion sort, but instead of shifting the elements like arrays, it arranges the pointers of nodes. Every node is traversed and inserted into a new sorted list. The function sortedInsert() is used to maintain the order.

Variants of Insertion Sort

There are mainly 2 variants of the insertion sort that can be implemented to make it efficient, which are discussed below.

1. Binary Insertion Sort in C

Binary Insertion Sort is an improved version of the Insertion Sort, and uses binary search to find the correct position to insert the current element, instead of doing a linear search like the regular insertion sort.

Output:

Explanation: The above C program improves the efficiency of normal insertion sort by using binary search to find the correct position for each element. It checks each element one by one, and then quickly finds the correct position of the element to insert it in the right place, hence, saving the comparison time.

2. Shell Sort in C

Shell Sort is an optimized version of Insertion Sort that improves its performance by allowing the exchange of the elements that are far apart. It can be thought of as an optimized version of Insertion Sort. It works well when elements are close to their correct position. The main key idea of the insertion sort is, 

Shell Sort = Insertion Sort + Gap Reduction Strategy

Now, let us discuss it with the help of an example.

Output:

Explanation: In the above C program, Shell Sort is implemented using the function shellSort(int arr[], int n). The function takes an array and the length of the array as input. The function uses the for loop to sort the array to its correct position by starting in the middle of the array.

Time and Space Complexity of Insertion Sort in C

Insertion Sort is a simple sorting algorithm that starts from the second element, and compares the current element with the elements that are present before it. It inserts the element into its correct position and continues till the entire array is sorted.

• The best-case complexity of the insertion sort comes when the array is already sorted in increasing order, i.e., each element is already greater than all the previous elements, so no shifting is needed.

• The average-case complexity of insertion sort occurs when the elements are in random order. In this case, some elements have to be shifted, while others may need to be shifted multiple times.

• The worst-case complexity of the insertion sort comes when the array is sorted in reverse order, as every element is smaller than all the previous elements. Hence, 

total comparisons = 1 + 2 + 3 + ... + (n−1) = n(n−1)/2, 

which comes to be O(n²).

Insertion Sort is an in-place sorting algorithm, as it does not use any extra data space, like arrays or lists. All sorting is done by swapping or shifting elements within the input array itself. It only uses a constant number of extra variables.

Note: The best case of binary insertion sort occurs when the array is already sorted.

Advantages of Insertion Sort in C

• Insertion Sort is simple and easy to implement, as it uses simple loops to sort an array.
• Insertion Sort is an in-place algorithm, i.e., it does not need any extra memory to sort the array.
• It is a stable sort algorithm, i.e., it keeps the equal elements in their original order.

Disadvantages of Insertion Sort in C

• Insertion Sort is slow for large datasets, i.e., it has the time complexity of O(n²) in the average and worst case.
• It is not suitable for large-scale sorting, as better algorithms like Merge Sort or Quick Sort are faster.
• It is not efficient when many elements need to be shifted, especially in reverse-sorted data.

Conclusion

From the above article, we conclude that insertion sort is a simple sorting technique that works well for small or nearly sorted datasets. It builds the final sorted array by inserting one element into its correct position. It is easy to understand and implement, but it is not suitable for large inputs due to its O(n²) time complexity. However, with small improvements like binary insertion, its performance can be enhanced. Insertion Sort is useful in real-world cases involving limited or structured data. If you want to learn more about the topic of insertion sort in C and other topics of DSA, you can refer to our DSA course on C.

Insertion Sort in C – FAQs