Suggest an editImprove this articleRefine the answer for “What is insertion sort (insertion sorts)?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)**Insertion sort** is a simple, stable, in-place algorithm that builds the sorted part of the array by inserting each next element into its correct position. It runs in O(n²) in the worst and average cases, and in O(n) in the best case (nearly sorted data). It fits small arrays, nearly sorted data, and works well as part of hybrid algorithms. **Key point:** the best case is O(n), not always O(n²) - adaptivity to nearly sorted data is the algorithm's main advantage.Shown above the full answer for quick recall.Answer (EN)Image## Short answer **Insertion sort** is a simple, stable, in-place algorithm that builds the sorted part of the array by inserting each next element into its correct position. It runs in O(n²) in the worst and average cases, and in O(n) in the best case (nearly sorted data). It fits small arrays, nearly sorted data, and works well as part of hybrid algorithms. ## Detailed breakdown ### Algorithm idea Imagine sorting playing cards in your hand in ascending order: you take a new card and insert it into the already sorted part so the order is preserved. The algorithm works the same way, moving through the array from left to right, maintaining a sorted prefix on the left and inserting the current element into it. ### Step-by-step algorithm 1. Assume the one-element subarray (the first element) is already sorted. 2. Take the next element (the key) and compare it with the elements of the sorted part from right to left. 3. Shift elements greater than the key one position to the right to make room. 4. Insert the key into the freed position. 5. Repeat for all elements. ### Code example (JavaScript) ``` function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { const key = arr[i]; let j = i - 1; // Shift elements to the right while they are greater than key while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } // Insert key into its position arr[j + 1] = key; } return arr; } // Optimization: binary insertion (fewer comparisons, same number of shifts) function binaryInsertionSort(arr) { for (let i = 1; i < arr.length; i++) { const key = arr[i]; let left = 0; let right = i; // half-open interval [left, right) // Find the insertion position via binary search while (left < right) { const mid = (left + right) >> 1; // <= places key after equal elements - keeps the sort stable if (arr[mid] <= key) left = mid + 1; else right = mid; } // Shift the block right by 1 to insert key for (let j = i; j > left; j--) arr[j] = arr[j - 1]; arr[left] = key; } return arr; } // Demonstration const nums = [5, 2, 4, 6, 1, 3]; console.log(insertionSort([...nums])); // [1,2,3,4,5,6] console.log(binaryInsertionSort([...nums])); // [1,2,3,4,5,6] ``` ### Complexity and properties - Time: worst/average case O(n²), best case O(n) for nearly sorted data (few inversions). - Memory: O(1) additional (in-place). - Stability: stable sort (equal elements keep their relative order). - Adaptivity: faster on nearly sorted arrays; the actual running time depends on the number of inversions. - Online property: you can maintain a sorted structure by inserting incoming elements one at a time. ### When to use - Small arrays (usually up to 20-50 elements) - low constants and simplicity. - Nearly sorted data - close to O(n). - In hybrid sorts: as a "finishing" pass for small subarrays after partitioning (for example, after quicksort). - Online updates of sorted collections, when elements arrive gradually. ### Variants and optimizations - Binary insertion sort: reduces the number of comparisons from O(n²) to O(n log n), but the number of shifts is still O(n²). - Sentinel: place the minimum element at the front in advance to remove boundary checks in the loop. - Shifts instead of swaps: use block shifts and a single write of the key - fewer write operations. - Linked lists: insertion can be O(1) at a known position, but finding the position is still O(n). - Relation to Shell sort: Shell sort is a generalization of insertion sort with decreasing "gap" intervals to reduce the number of shifts. ### Comparison with bubble sort and selection sort - Bubble sort vs insertion sort: both are O(n²), but insertion sort usually makes fewer unnecessary swaps and is faster on nearly sorted arrays; bubble sort can be optimized to O(n) on sorted data, but its constants are higher. - Selection sort vs insertion sort: selection sort makes O(n) swaps but always O(n²) comparisons and is not stable (in its classic form); insertion sort is stable and adaptive. ### Invariant and correctness Invariant: after the i-th iteration, the subarray [0..i) is sorted. Inserting the i-th element preserves the invariant, because all elements greater than key are shifted, and key is placed into the single position where it belongs. When the loop finishes at i = n, the array is sorted. ### Common interview mistakes - Using swaps instead of shifts - more writes and worse performance. - Boundary mistakes: forgetting to insert key after the comparison loop ends (need arr[j + 1] = key). - Losing stability: a wrongly chosen comparison condition in binary insertion. - Misunderstanding adaptivity: the best case is O(n), not always O(n²).For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.