Insertion sort
Insertion sort is a simple, in-place comparison-based sorting algorithm that constructs the final sorted array one element at a time by iteratively inserting each unsorted element into its correct position within the already sorted prefix of the array.[1] It begins with the first element considered sorted and then, for each subsequent element, shifts larger elements in the sorted portion to the right until the correct insertion point is found, after which the element is placed there.[2] This process mimics manual sorting, such as organizing playing cards into order by inserting each new card into a growing sorted hand.[3]
The algorithm's time complexity is O(n) in the best case, when the input is already sorted or nearly sorted, requiring only n-1 comparisons with no shifts.[4] However, in the average and worst cases—such as a reverse-sorted array—it requires O(n²) comparisons and shifts, making it quadratic and inefficient for large datasets.[1] Despite this, insertion sort is stable, preserving the relative order of equal elements, and uses constant extra space beyond the input array.[2] It excels in scenarios with small arrays or partially sorted data, where its simplicity and low overhead provide practical advantages over more complex algorithms.[5]
Insertion sort serves as a foundational example in computer science education for understanding sorting principles and loop invariants, and it forms a building block in hybrid algorithms like Shellsort, which applies it after preliminary gap-based sorting.[1] Its pseudocode is straightforward, typically implemented with nested loops: an outer loop iterates over each element starting from the second, and an inner loop shifts elements rightward while comparing.[2]
Fundamentals
Definition and Intuition
Insertion sort is a simple comparison-based sorting algorithm that builds the sorted portion of an array one element at a time by taking each unsorted element and inserting it into its correct position within the already sorted subarray.[6][7]
As a comparison-based method, insertion sort determines the order of elements solely through pairwise comparisons, without relying on the specific values beyond their relative ordering.[8] The algorithm intuitively resembles the process of sorting a hand of playing cards: one starts with the cards face down on the table and an empty hand, then picks up each card one by one and inserts it into the proper position among the cards already held in sorted order.[9]
To illustrate, consider a four-element array initially in an unsorted state: [5, 2, 4, 1]. The first element, 5, forms the initial sorted subarray by itself. The next element, 2, is then compared and inserted before 5, yielding [2, 5, 4, 1] after the first insertion.[10]
This approach yields a quadratic time complexity in the worst case, though full analysis is covered elsewhere.[6]
Historical Background
Insertion sort traces its origins to 1946, when John Mauchly, co-designer of the ENIAC computer, first described a variant using binary insertion during a presentation at the Moore School Lectures, the first comprehensive series on the design of electronic digital computers.[11] This mention positioned insertion sort as one of the earliest sorting algorithms conceptualized for electronic computers, emerging amid the transition from mechanical to digital computation in the mid-20th century. Although formalized later, its core idea of incrementally building a sorted sequence mirrored longstanding manual practices.
By the 1960s, insertion sort had earned recognition as an essential educational tool in emerging algorithms curricula, valued for its simplicity and direct illustration of sorting principles without advanced data structures. Its prominence solidified in 1973 with Donald Knuth's The Art of Computer Programming, Volume 3: Sorting and Searching, which analyzed it as a baseline method and referenced its historical roots, cementing its role in computer science pedagogy. Unlike some contemporary algorithms, insertion sort was never patented, remaining freely available and influencing subsequent computational techniques.
Algorithm
Step-by-Step Execution
Insertion sort operates by maintaining a sorted prefix of the array, starting with the first element considered sorted by default. For each subsequent element at position j (from 2 to n), the algorithm stores this element in a temporary variable known as the key. It then iterates backward through the sorted prefix (from i = j-1 downward), shifting any element greater than the key one position to the right until it identifies the appropriate insertion point, at which the key is placed. This inner loop ensures that the prefix remains sorted after each insertion.[12]
The key variable temporarily holds the element under consideration, preventing it from being overwritten during shifts, while the inner loop performs the comparisons and rightward movements of larger elements to create space for insertion. This mechanism guarantees that elements are compared and repositioned relative to the already sorted portion, building the solution incrementally.[12]
To demonstrate the execution, consider the initial array A = [5, 2, 4, 6, 1, 3]. The process unfolds over five passes (for j = 2 to $6), with array states shown after each insertion. This example mirrors the card-sorting intuition, where each new "card" is slid into its proper place among the sorted ones.[12]
| Pass | j | Key | Final i | Shifts Performed | Array State After Insertion |
|---|
| Initial | - | - | - | None | [5, 2, 4, 6, 1, 3] |
| 1 | 2 | 2 | 0 | Shift 5 right | [2, 5, 4, 6, 1, 3] |
| 2 | 3 | 4 | 1 | Shift 5 right | [2, 4, 5, 6, 1, 3] |
| 3 | 4 | 6 | 3 | None | [2, 4, 5, 6, 1, 3] |
| 4 | 5 | 1 | 0 | Shift 6, 5, 4, 2 right | [1, 2, 4, 5, 6, 3] |
| 5 | 6 | 3 | 1 | Shift 6, 5, 4 right | [1, 2, 3, 4, 5, 6] |
Pseudocode Representation
The standard pseudocode for the insertion sort algorithm, assuming 0-based indexing, is presented below. This formulation iterates through the array starting from the second element and inserts each one into its correct position within the already sorted prefix by shifting larger elements to the right.
for i = 1 to n-1
key = A[i]
j = i - 1
while j >= 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j+1] = key
for i = 1 to n-1
key = A[i]
j = i - 1
while j >= 0 and A[j] > key
A[j+1] = A[j]
j = j - 1
A[j+1] = key
The outer loop, for i = 1 to n-1, selects each unsorted element from the second position to the end of the array as the key to be inserted. The inner while loop then shifts all elements in the sorted prefix that are greater than the key one position to the right, effectively finding the insertion point before placing the key there.
This pseudocode assumes the input is an array A of n elements, typically integers, indexed from 0 to n-1, and sorts them in non-decreasing order; it is generalizable to other comparable data types such as real numbers or strings by adjusting the comparison operator.
To adapt the algorithm for sorting in descending order, the comparison condition in the while loop can be reversed from A[j] > key to A[j] < key, which shifts smaller elements to the right instead.[13]
Time Complexity Cases
The time complexity of insertion sort varies depending on the input arrangement, primarily measured by the number of comparisons and swaps (or shifts) performed. In the best case, when the input array is already sorted, the algorithm requires exactly n-1 comparisons, as each new element is immediately inserted at the end of the sorted subarray without any shifts, and zero swaps occur, yielding a linear time complexity of O(n).[14][4]
In the worst case, which arises with a reverse-sorted input, each new element must be compared against all previous elements in the sorted subarray and shifted to the beginning, leading to approximately n^2/2 comparisons and n^2/2 swaps. The exact number of comparisons is given by the summation \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}, derived from the arithmetic series formula where the i-th iteration performs i comparisons, resulting in a quadratic time complexity of O(n^2).[14][4]
For the average case over random permutations of the input, the expected number of comparisons is approximately n^2/4, based on the average number of inversions being \binom{n}{2}/2 = n(n-1)/4, with each inversion contributing to a comparison and shift, leading to a tight bound of \Theta(n^2) time complexity.[14]
Insertion sort exhibits an adaptive nature, performing fewer operations on partially sorted data compared to fully random or reverse-ordered inputs, as the position of each insertion depends on the existing order in the sorted subarray.[14]
Space Complexity and Stability
Insertion sort is an in-place sorting algorithm, meaning it sorts the input array without requiring additional storage proportional to the input size, resulting in an auxiliary space complexity of O(1). This efficiency stems from its reliance on only a constant number of extra variables, such as the temporary variable for the key element being inserted and an index variable j to track the position in the sorted subarray.[10]
The algorithm is stable, preserving the relative order of elements with equal keys as they appear in the original input. Stability is ensured because the insertion process shifts elements in the sorted subarray only when they are strictly greater than the key; equal elements are not shifted past the key, thereby maintaining their original sequence.[15] To illustrate, consider an array where two equal values occupy positions i and k (i < k); during sorting, the element at k will be inserted without displacing the one at i if they match, as the comparison condition (A[j-1] > key) fails for equals.[15]
While the in-place property benefits array implementations by minimizing memory overhead, adaptations for linked lists retain O(1) auxiliary space through pointer manipulations alone, though the total space usage includes the overhead of node pointers inherent to the list structure. This trade-off highlights insertion sort's versatility across data structures without escalating auxiliary requirements.[16][17]
Comparisons
Relation to Selection and Bubble Sort
Insertion sort shares several characteristics with selection sort, making both suitable as introductory algorithms for understanding basic sorting mechanics. Both algorithms operate in-place with a time complexity of O(n²) in the average and worst cases, requiring a linear scan of the array during each pass and performing swaps or shifts to reorder elements.[18] They are often used educationally to illustrate the concept of iterative element placement through comparisons and exchanges.[19]
Despite these similarities, insertion sort and selection sort differ in their core approaches and adaptability. Insertion sort incrementally builds a sorted prefix by inserting each new element into its correct position within the existing sorted portion, potentially shifting multiple elements.[18] In contrast, selection sort identifies the minimum element in the unsorted portion during each pass and swaps it directly into the next position in the sorted prefix, without intermediate shifts.[20] Insertion sort is adaptive, achieving O(n time in the best case for nearly sorted inputs, whereas selection sort maintains O(n²) performance regardless of input order.[18]
Insertion sort also exhibits parallels with bubble sort, particularly in their use of adjacent element comparisons and visualization as element "movement" through the array. Both algorithms can be interpreted as propagating elements toward their final positions via pairwise checks, and they are stable, preserving the relative order of equal elements.[21]
However, the mechanics diverge in efficiency and operation. Insertion sort performs shifts of multiple elements in a single insertion step to maintain the sorted prefix, often resulting in fewer total writes than bubble sort's repeated pairwise adjacent swaps.[20] Bubble sort relies on multiple passes of adjacent interchanges to "bubble" elements to their positions, which can lead to more exchanges on average, though insertion sort generally executes fewer operations overall in typical scenarios.[18]
To illustrate these aspects for a small array of size n=5, the following table compares key metrics in the worst case (reverse sorted input), assuming standard implementations without early termination optimizations:
| Property | Insertion Sort | Selection Sort | Bubble Sort |
|---|
| Number of Passes | 4 | 4 | 4 |
| Number of Comparisons | 10 | 10 | 10 |
| Number of Swaps/Shifts | 10 | 4 | 10 |
| Best-Case Adaptability | O(n) | O(n²) | O(n²) |
Relation to Advanced Algorithms
Insertion sort serves as a foundational component in hybrid sorting algorithms, where it is employed as a base case for small subarrays (typically of size n < 10–20) to leverage its low overhead and efficiency on limited data.[22] In introsort, a hybrid of quicksort and heapsort designed to guarantee O(n log n) worst-case performance, insertion sort is applied in a final pass over small subarrays after partitioning, avoiding the recursive overhead of quicksort on tiny inputs while preserving average-case speed.[23] Similarly, timsort—a stable hybrid used in languages like Python and Java—identifies or constructs short "runs" (sorted subsequences) and extends any shorter than a minimum size using insertion sort before merging them efficiently, capitalizing on insertion sort's speed for small, nearly sorted segments.[24]
Insertion sort exhibits conceptual parallels with merge sort in the incremental construction of sorted segments from unsorted data, but contrasts in its in-place operation via element shifting rather than merge sort's use of auxiliary space for combining sorted halves.[6] Merge sort achieves stability through the merge process, which preserves relative order, whereas insertion sort maintains stability by inserting elements into an existing sorted prefix without disrupting equal-element ordering.[6]
Unlike quicksort, which introduces randomness via pivot selection—resulting in instability and vulnerability to O(n²) worst-case behavior on adversarial inputs—insertion sort is fully deterministic and stable, making it superior for nearly sorted datasets where it achieves linear time complexity.[25]
Shell sort extends insertion sort as a generalization by performing insertions on interleaved subarrays separated by diminishing gaps (e.g., starting from n/2 and reducing), which reduces inversions early and approaches O(n log n) efficiency in practice, serving as a bridge to advanced comparison-based sorters.
In resource-constrained environments like embedded systems, insertion sort is favored over quicksort for its straightforward iterative implementation, minimal memory footprint, and lack of recursion depth issues that could lead to stack overflows.[26]
Variants and Extensions
Binary Insertion Sort
Binary insertion sort is a variant of the standard insertion sort algorithm that optimizes the search for the insertion position by replacing the linear scan with a binary search on the sorted prefix of the array. This change reduces the number of comparisons needed to locate where the current element should be placed while preserving the overall insertion process of shifting elements to make room. The approach was first analyzed in detail as an efficient method for minimizing comparisons in internal sorting routines.[27]
In this variant, for each element starting from the second position, a binary search is conducted over the previously sorted subarray to find the precise index for insertion. The binary search halves the search space iteratively by comparing the key element with the middle element of the current range, adjusting the bounds accordingly to identify the first position greater than the key. After determining this position, the elements from that index to the current position are shifted rightward in a single linear pass, and the key is placed in the vacated spot. This maintains the sorted order of the prefix after each insertion.[28]
The key benefit of binary insertion sort lies in its comparison efficiency: while standard insertion sort requires up to O(n^2) comparisons in the worst case, this variant achieves approximately O(n \log n) total comparisons by leveraging the logarithmic time of binary search for each of the n insertions. This makes it particularly advantageous in scenarios where comparisons are computationally expensive relative to memory operations, such as sorting strings or complex objects. However, the overall time complexity remains O(n^2) due to the unavoidable linear shifts, which still total O(n^2) assignments in the worst case.[27][28]
Despite the optimization, binary insertion sort offers limited practical speedup for random inputs on modern hardware, where the cost of array shifts often dominates over saved comparisons. It excels, however, on nearly sorted arrays, where shifts are minimal, or in environments where comparison overhead is high. The algorithm is also stable, ensuring that equal elements retain their relative order from the input, as the binary search identifies the insertion point immediately after all elements less than or equal to the key without disturbing preceding equals.[28][29]
The following pseudocode illustrates the binary insertion sort, with the binary search implemented to find the first position strictly greater than the key for stability:
for i from 1 to length(a) - 1
key ← a[i]
low ← 0
high ← i - 1
while low ≤ high
mid ← floor((low + high) / 2)
if a[mid] > key
high ← mid - 1
else
low ← mid + 1
pos ← low
for j from i downto pos + 1
a[j] ← a[j - 1]
a[pos] ← key
for i from 1 to length(a) - 1
key ← a[i]
low ← 0
high ← i - 1
while low ≤ high
mid ← floor((low + high) / 2)
if a[mid] > key
high ← mid - 1
else
low ← mid + 1
pos ← low
for j from i downto pos + 1
a[j] ← a[j - 1]
a[pos] ← key
Shell Sort as a Generalization
Shell sort generalizes the insertion sort algorithm by applying it to multiple subarrays defined by a sequence of decreasing gaps, or increments, which allows for more efficient handling of distant elements early in the process and reduces the number of inversions before the final insertion sort pass with gap 1.[30] This approach addresses the limitation of standard insertion sort, where elements can only move one position at a time, by enabling larger swaps initially to bring the array closer to sorted order.[31]
The algorithm proceeds by selecting a sequence of gaps, starting with a large value such as h = \lfloor n/2 \rfloor and halving it repeatedly until h = 1, as proposed in the original formulation. For each gap h, insertion sort is performed independently on every subarray consisting of elements spaced h positions apart (i.e., for each starting index i from 0 to h-1, sort the elements at positions i, i+h, i+2h, \ldots). This creates a cascading effect where early passes with larger gaps move elements farther, facilitating quicker convergence in later passes. The method was invented by Donald Shell in 1959 and termed the "diminishing increment sort."[31][30]
In terms of performance, shell sort retains the worst-case time complexity of O(n^2) like insertion sort, occurring when the gap sequence does not sufficiently reduce inversions. However, its average-case performance improves significantly over plain insertion sort for large n, ranging from O(n^{1.3}) to O(n \log^2 n) depending on the choice of gap sequence; for instance, Shell's original powers-of-two gaps yield approximately O(n^{3/2}), while optimized sequences like those proposed by Sedgewick achieve closer to O(n^{4/3}). This makes shell sort particularly effective for moderately large datasets where adaptive sorting benefits from the initial disorder reduction.[30]
Consider an example with the array [5, 2, 4, 6, 1, 3] where n = 6, using gaps 3 and then 1:
-
For gap h = 3:
-
For gap h = 1: Perform standard insertion sort on [5, 1, 3, 6, 2, 4], resulting in the fully sorted array [1, 2, 3, 4, 5, 6].
This illustrates how the initial gap pass rearranges distant elements, easing the work of the final insertion.[30]
Implementations
Array-Based Example
The array-based implementation of insertion sort operates on a contiguous array by iteratively inserting each element into its correct position within the sorted prefix, shifting larger elements to the right as needed. This approach leverages array indices for efficient access and modification, making it suitable for static data structures. The following C code provides a standard implementation, directly translating the core pseudocode logic into executable form.Introduction to Algorithms, 3rd Edition, MIT Press, 2009
c
#include <stdio.h>
// Function to perform insertion sort on an integer array
void insertionSort(int arr[], int n) {
// Outer [loop](/page/Loop) starts from the second element (index 1), as the first element is already sorted
for (int i = 1; i < n; i++) {
// Store the current element to be inserted (the 'key')
int key = arr[i];
// Initialize pointer to the last element in the sorted prefix
int j = i - 1;
// Shift elements greater than the key one position to the right
// Continue while the key is smaller than the previous element and we haven't reached the start
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // Move the larger element to the next position
j--; // Move the pointer left
}
// Insert the key into its correct position
arr[j + 1] = key;
}
}
// Helper function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
// Example array: unsorted input
int arr[] = {5, 2, 4, 6, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
// Sort the array
insertionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
#include <stdio.h>
// Function to perform insertion sort on an integer array
void insertionSort(int arr[], int n) {
// Outer [loop](/page/Loop) starts from the second element (index 1), as the first element is already sorted
for (int i = 1; i < n; i++) {
// Store the current element to be inserted (the 'key')
int key = arr[i];
// Initialize pointer to the last element in the sorted prefix
int j = i - 1;
// Shift elements greater than the key one position to the right
// Continue while the key is smaller than the previous element and we haven't reached the start
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // Move the larger element to the next position
j--; // Move the pointer left
}
// Insert the key into its correct position
arr[j + 1] = key;
}
}
// Helper function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
// Example array: unsorted input
int arr[] = {5, 2, 4, 6, 1, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
// Sort the array
insertionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
This code handles sorting of integer arrays in ascending order. The main function demonstrates usage with the input array [5, 2, 4, 6, 1, 3], which outputs the original and sorted versions ([1, 2, 3, 4, 5, 6]) when compiled and run using a standard C compiler like GCC. For extending to generic types (e.g., floats or custom objects), the implementation can be adapted using C++ templates while preserving the same shifting logic.Introduction to Algorithms, 3rd Edition, MIT Press, 2009
Linked List Adaptation
The adaptation of insertion sort to singly linked lists maintains the core principle of building a sorted sublist incrementally by inserting elements one at a time, but leverages pointer manipulations instead of index-based shifts. In this version, the algorithm traverses the input list, removes each node temporarily, and inserts it into the appropriate position within a growing sorted sublist by comparing values and updating the next pointers of adjacent nodes. This approach is particularly suited for singly linked lists, where random access is unavailable, and all operations proceed sequentially from the head.
To implement this, a common strategy uses a dummy head node to simplify pointer updates at the beginning of the sorted sublist, though it is optional. The pseudocode below outlines the process, assuming a Node structure with data and next fields:
[Node](/page/Node)* insertionSort([Node](/page/Node)* head) {
if (head == NULL || head->next == NULL) return head;
[Node](/page/Node)* sorted = NULL; // Head of the sorted sublist
[Node](/page/Node)* current = head;
while (current != NULL) {
[Node](/page/Node)* next = current->next; // Store next to avoid losing the rest of the list
insertIntoSorted(current, &sorted); // Insert current into sorted sublist
current = next;
}
return sorted;
}
void insertIntoSorted(Node* newNode, Node** sortedHead) {
if (*sortedHead == NULL || newNode->data < (*sortedHead)->data) {
newNode->next = *sortedHead;
*sortedHead = newNode;
return;
}
Node* current = *sortedHead;
while (current->next != NULL && current->next->data <= newNode->data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
[Node](/page/Node)* insertionSort([Node](/page/Node)* head) {
if (head == NULL || head->next == NULL) return head;
[Node](/page/Node)* sorted = NULL; // Head of the sorted sublist
[Node](/page/Node)* current = head;
while (current != NULL) {
[Node](/page/Node)* next = current->next; // Store next to avoid losing the rest of the list
insertIntoSorted(current, &sorted); // Insert current into sorted sublist
current = next;
}
return sorted;
}
void insertIntoSorted(Node* newNode, Node** sortedHead) {
if (*sortedHead == NULL || newNode->data < (*sortedHead)->data) {
newNode->next = *sortedHead;
*sortedHead = newNode;
return;
}
Node* current = *sortedHead;
while (current->next != NULL && current->next->data <= newNode->data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
This pseudocode starts with an empty sorted sublist and iteratively removes nodes from the input list, finding the insertion point via a linear traversal of the sorted sublist and linking the node in place.[32]
A key benefit of this linked list adaptation is the efficiency of insertions: once the position is identified, updating pointers takes constant O(1) time, avoiding the O(n) element shifts required in array-based versions that copy data to make space. This makes it ideal for dynamic data structures where elements are non-contiguous in memory, such as in scenarios involving frequent node additions or removals during sorting. However, the overall time complexity remains O(n²) in the worst and average cases due to the nested traversals needed to locate each insertion point in the growing sorted sublist. Additionally, while the algorithm can be implemented in-place by modifying links without extra storage beyond a few pointers, building a separate sorted sublist may require careful management to reuse the original nodes.
Consider an example with the unsorted singly linked list 5 → 2 → 4 → 6 → 1 → 3. The algorithm begins with an empty sorted sublist. The first node (5) becomes the initial sorted sublist: 5. Next, node 2 is removed and compared: since 2 < 5, it is inserted at the front, yielding 2 → 5. Then, node 4 is inserted between 2 and 5 (after traversing to find 2 < 4 < 5), resulting in 2 → 4 → 5. Continuing, 6 is placed at the end (after 5), giving 2 → 4 → 5 → 6; 1 is inserted at the front (1 < 2), yielding 1 → 2 → 4 → 5 → 6; and finally 3 is inserted between 2 and 4, producing the fully sorted list 1 → 2 → 3 → 4 → 5 → 6. Each insertion involves pointer adjustments, such as updating the next field of the previous node to point to the new node and the new node's next to the subsequent node.