Sorting Algorithms- 3 - Algorithms - Computer Science Engineering (CSE)

Insertion Sort

Insertion sort is a simple comparison-based sorting algorithm that works much like the way one sorts playing cards in hand. The array is divided conceptually into a sorted part at the left and an unsorted part at the right. At each step, the algorithm picks the first element of the unsorted part and inserts it into its correct position in the sorted part by shifting larger elements one position to the right.

Algorithm (High-level)

To sort an array of size n in ascending order:

1. Iterate i from 1 to n-1 over the array (considering 0-based indexing).
2. Let key = arr[i]. Compare the key with elements in the sorted subarray arr[0..i-1].
3. While elements in arr[0..i-1] are greater than the key, shift them one position to the right and insert the key at the correct position.

Procedure (Pseudocode)

for i = 1 to n-1 key = arr[i] j = i - 1 while j >= 0 and arr[j] > key arr[j + 1] = arr[j] j = j - 1 arr[j + 1] = key

Worked Example

Sort the array: 12, 11, 13, 5, 6

Iteration-by-iteration state (0-based indices):

Initial: 12, 11, 13, 5, 6 i = 1, key = 11 Compare key with arr[0] = 12. Since 12 > 11, shift 12 right and insert 11. Result: 11, 12, 13, 5, 6 i = 2, key = 13 Compare key with arr[1] = 12. Since 12 < 13, no shift required. Result: 11, 12, 13, 5, 6 i = 3, key = 5 Compare key with arr[2] = 13. Shift 13 to right. Compare with arr[1] = 12. Shift 12 to right. Compare with arr[0] = 11. Shift 11 to right. Insert 5 at start. Result: 5, 11, 12, 13, 6 i = 4, key = 6 Compare with arr[3] = 13. Shift 13. Compare with arr[2] = 12. Shift 12. Compare with arr[1] = 11. Shift 11. Compare with arr[0] = 5. Since 5 < 6, stop and insert after 5. Result: 5, 6, 11, 12, 13

Implementations

• C++

  // C++ program for insertion sort #include <bits/stdc++.h> using namespace std; /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // A utility function to print an array of size n void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } /* Driver code */ int main() { int arr[] = { 12, 11, 13, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); printArray(arr, n); return 0; } // This code is contributed by rathbhupendra

• C

  // C program for insertion sort #include <math.h> #include <stdio.h> /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // A utility function to print an array of size n void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", arr[i]); printf("
"); } /* Driver program to test insertion sort */ int main() { int arr[] = { 12, 11, 13, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); printArray(arr, n); return 0; }

• Java

  // Java program for implementation of Insertion Sort class InsertionSort { /*Function to sort array using insertion sort*/ void sort(int arr[]) { int n = arr.length; for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } /* A utility function to print array of size n*/ static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } // Driver method public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6 }; InsertionSort ob = new InsertionSort(); ob.sort(arr); printArray(arr); } } /* This code is contributed by Rajat Mishra. */

• Python

  # Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)): print ("% d" % arr[i]) # This code is contributed by Mohit Kumra

• C#

  // C# program for implementation of Insertion Sort using System; class InsertionSort { // Function to sort array // using insertion sort void sort(int[] arr) { int n = arr.Length; for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; // Move elements of arr[0..i-1], // that are greater than key, // to one position ahead of // their current position while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // A utility function to print // array of size n static void printArray(int[] arr) { int n = arr.Length; for (int i = 0; i < n; ++i) Console.Write(arr[i] + " "); Console.Write("
"); } // Driver Code public static void Main() { int[] arr = { 12, 11, 13, 5, 6 }; InsertionSort ob = new InsertionSort(); ob.sort(arr); printArray(arr); } } // This code is contributed by ChitraNayal.

• PHP

  <?php // PHP program for insertion sort // Function to sort an array // using insertion sort function insertionSort(&$arr, $n) { for ($i = 1; $i < $n; $i++) { $key = $arr[$i]; $j = $i-1; // Move elements of arr[0..i-1], // that are greater than key, to // one position ahead of their // current position while ($j >= 0 && $arr[$j] > $key) { $arr[$j + 1] = $arr[$j]; $j = $j - 1; } $arr[$j + 1] = $key; } } // A utility function to // print an array of size n function printArray(&$arr, $n) { for ($i = 0; $i < $n; $i++) echo $arr[$i]." "; echo "
"; } // Driver Code $arr = array(12, 11, 13, 5, 6); $n = sizeof($arr); insertionSort($arr, $n); printArray($arr, $n); // This code is contributed by ChitraNayal. ?>

• Javascript

  <script> // Javascript program for insertion sort // Function to sort an array using insertion sort function insertionSort(arr, n) { let i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // A utility function to print an array of size n function printArray(arr, n) { let i; for (i = 0; i < n; i++) document.write(arr[i] + " "); document.write("<br>"); } // Driver code let arr = [12, 11, 13, 5, 6 ]; let n = arr.length; insertionSort(arr, n); printArray(arr, n); // This code is contributed by Mayank Tyagi </script>

Output

5 6 11 12 13

Time and Space Complexity

• Best case: O(n) - occurs when the array is already sorted. Only one comparison per element is needed and no shifts are required.
• Average case: O(n^2) - on average about n^2/4 comparisons and shifts.
• Worst case: O(n^2) - occurs when the array is sorted in reverse order; every insertion requires shifting all previously sorted elements.
• Auxiliary space: O(1) - insertion sort performs sorting in place using a constant amount of extra memory.

Properties

• Stable: Yes - equal elements retain their relative order because insertion places new equal elements after existing ones from left to right.
• In-place: Yes - it requires no extra array, only a few variables.
• Online: Yes - it can sort a list as it receives it (useful for streaming data insertion where items arrive one by one).
• Algorithmic paradigm: Incremental / incremental construction of the sorted sequence.
• Adaptive: Partially - its running time improves for inputs that are already (or nearly) sorted.
• When to use: For small arrays, nearly sorted arrays, or when stability and in-place behaviour are required. Often used as the terminal sort within optimized hybrid algorithms (e.g., when subarray sizes become small in quicksort or mergesort).

Boundary Cases

• Insertion sort takes maximum time to sort when elements are sorted in reverse order.
• Insertion sort takes minimum time (Θ(n)) when elements are already sorted.

Binary Insertion Sort

Binary Insertion Sort reduces the number of comparisons by using binary search to find the correct insertion position in the sorted subarray. For the i-th insertion, a binary search in arr[0..i-1] locates the position in O(log i) comparisons. However, shifting elements to make room for the key still takes O(i) time in the worst case. Therefore the overall worst-case running time remains O(n^2), but the number of comparisons decreases.

Complexities:

• Comparisons: O(n log n) in total (approximately), because each insertion uses O(log i) comparisons.
• Shifts/moves: O(n^2) in total in the worst case.
• Overall time: O(n^2).

Binary insertion sort is helpful when comparisons are expensive but moving elements is cheap.

Insertion Sort on a Linked List

Insertion sort can be implemented efficiently on a linked list because insertion at a known location is O(1). The algorithm avoids the element-shifting cost inherent to arrays, but it still must search for the correct insertion point, which requires traversal. The typical approach:

1. Create an empty sorted (result) list.
2. Traverse the original list node by node. For each current node:
   • Find the correct position in the sorted list by traversing from the head of the sorted list.
   • Insert the current node in the sorted list (adjust pointers).
3. After processing all nodes, the sorted list becomes the result; update the head pointer.

Complexities for singly linked list:

• Time (worst-case): O(n^2) - for each node we may traverse nearly the whole sorted list.
• Space: O(1) auxiliary space (reusing nodes).
• Advantages: No element shifting; straightforward pointer manipulation; stable.

Notes and Practical Use

• Insertion sort is one of the simplest sorts and is often used when input size is small (for example, arrays of size < 20) or when the data is almost sorted.
• Many hybrid sorting algorithms use insertion sort as a base case for small subarrays because of its low overhead and good cache performance.
• Insertion sort is stable and preserves the relative order of equal elements, which is important in some applications (e.g., when sorting records by multiple keys).

Summary

Insertion sort builds the final sorted array one item at a time by inserting each new item into its correct position. It is simple, stable, in-place, and efficient for small or nearly sorted inputs, though its worst-case time complexity is O(n^2). Variants such as binary insertion sort reduce comparisons but not overall time complexity; using linked lists removes the need to shift elements but still results in O(n^2) time due to traversal cost.