The insertion sort algorithm sorts a list by growing a sorted section one element at a time. Use the visualization below to run it, pause it, step through it, and step backward to see exactly how each key slides into place.
Operation log
Sorted part
Complexity (theory): best O(n), average O(n²), worst O(n²). Extra space O(1). Stable and in place. The counters above are measured for your array only.
What Is the Insertion Sort Algorithm?
Insertion sort is a simple comparison-based sorting algorithm. It works like sorting playing cards in your hand: you pick up the next card and slide it left until it sits in the right spot among the cards you already hold. At every moment, the left part of the array is sorted and the right part is not yet processed.
Because it is easy to read, easy to write, and runs in place, insertion sort is often the first sorting algorithm students learn. It is also genuinely useful for small or nearly sorted data, which is why faster algorithms often use it as a helper.
How Insertion Sort Works: Steps, Example and Code
How Insertion Sort Works Step by Step
- Treat the first element as a sorted part of size one.
- Take the next element. This element is called the key.
- Compare the key with the element on its left.
- If the left element is larger, move the key one place left, and compare again.
- Stop when the left element is smaller or equal, or when the key reaches the start of the array.
- The key is now in the correct place, so the sorted part has grown by one.
- Repeat until every element has been inserted.
The classic version shifts larger elements one place to the right and drops the key into the gap. The visualization above moves the key left with adjacent swaps instead, so every bar stays visible. Both versions make the same comparisons and produce the same result.
Insertion Sort Example With a Step-by-Step Walkthrough
Sort the array [5, 2, 4, 6, 1, 3].
- Key 2: 5 is larger, so 2 moves left. Array: [2, 5, 4, 6, 1, 3].
- Key 4: 5 is larger, so 4 moves left. 2 is smaller, so it stops. Array: [2, 4, 5, 6, 1, 3].
- Key 6: 5 is smaller, so 6 stays. Array: [2, 4, 5, 6, 1, 3].
- Key 1: it moves left past 6, 5, 4 and 2. Array: [1, 2, 4, 5, 6, 3].
- Key 3: it moves left past 6, 5 and 4, then stops because 2 is smaller. Array: [1, 2, 3, 4, 5, 6].
Notice that the sorted part grows by one element every round, but elements inside it can still move when a smaller key arrives.
Insertion Sort Pseudocode
insertionSort(A):
for i = 1 to length(A) - 1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j] // shift larger element right
j = j - 1
A[j + 1] = key // drop the key into the gapThe outer loop picks each key. The inner loop shifts every larger element one step to the right. Using a strict greater-than test (not greater-or-equal) keeps equal elements in their original order.
Insertion Sort Implementation in JavaScript
function insertionSort(input) {
const a = [...input]; // copy: the input is not modified
for (let i = 1; i < a.length; i++) {
const key = a[i];
let j = i - 1;
while (j >= 0 && a[j] > key) { // strict ">" keeps the sort stable
a[j + 1] = a[j]; // shift right
j--;
}
a[j + 1] = key; // insert the key
}
return a;
}The function handles an empty array and a one-element array without special code, because the loop never runs. It copies the input first, so the original array stays unchanged.
Insertion Sort Time and Space Complexity
Time Complexity of Insertion Sort
The work depends on how out of order the data is. Each shift fixes exactly one inversion (a pair of elements in the wrong order), so the total number of shifts equals the number of inversions. A sorted array has none, and a reverse-sorted array has the maximum, about n²/2.
| Case | Time | When it happens |
|---|---|---|
| Best | O(n) | Already sorted: one comparison per element |
| Average | O(n²) | Randomly ordered data |
| Worst | O(n²) | Reverse sorted: every key moves to the front |
Space Complexity of Insertion Sort
Insertion sort sorts in place and needs only a few extra variables (the key and two indexes), so its auxiliary space is O(1). It does not use recursion, so there is no stack growth.
Insertion Sort Advantages, Disadvantages and Comparisons
Advantages and Disadvantages of Insertion Sort
Advantages: it is simple, stable, in place, and adaptive, meaning it speeds up on nearly sorted data. It is also online, so it can sort items as they arrive.
Disadvantages: its O(n²) average and worst time makes it slow for large random inputs, where algorithms such as merge sort or quick sort are much faster.
Insertion Sort vs Bubble Sort vs Selection Sort
| Feature | Insertion | Bubble | Selection |
|---|---|---|---|
| Best case | O(n) | O(n) with early exit | O(n²) |
| Worst case | O(n²) | O(n²) | O(n²) |
| Stable | Yes | Yes | Usually no |
| Writes | Many shifts | Many swaps | Few swaps |
| Typical verdict | Best of the three for small or nearly sorted data | Mostly educational | Useful when writes are costly |
Using Insertion Sort in Practice: Applications and Mistakes
Common Applications of Insertion Sort
- Sorting small arrays, where its low overhead beats more complex algorithms.
- Finishing nearly sorted data after another step has done most of the work.
- Hybrid algorithms: many production sorts switch to an insertion-style method for small pieces.
- Online sorting, where items arrive one at a time and the list must stay sorted.
Common Mistakes When Implementing Insertion Sort
- Starting the outer loop at index 0 instead of 1, which wastes a pass.
- Overwriting the key before saving it in a variable.
- Using a greater-or-equal test, which makes the sort unstable.
- Checking j > 0 instead of j >= 0 in the shifting version, which skips the first element.
- Forgetting to test sorted, reverse-sorted, duplicate-heavy and single-element arrays.
Insertion Sort Variations and Optimizations
The basic insertion sort algorithm has several well-known refinements. Knowing them shows where insertion sort fits among other sorting algorithms.
Binary Insertion Sort
Standard insertion sort finds the insertion point by comparing the key with each element on its left. Binary insertion sort uses binary search on the sorted part instead, so it needs only about log₂ i comparisons for the i-th element. Total comparisons drop to O(n log n). The elements must still be shifted, so the running time stays O(n²). This variation helps when comparing two items is expensive, such as comparing long strings, but moving items is cheap.
Insertion Sort on Linked Lists
On a linked list, inserting a node needs no shifting, because you only change two pointers. Finding the position still takes O(n) steps, so the total stays O(n²). It does avoid moving large records around in memory.
Shell Sort: Insertion Sort With Gaps
Shell sort first sorts elements that are far apart, using a gap, and then shrinks the gap step by step until it reaches 1. The last pass is an ordinary insertion sort, but by then the array is nearly sorted, so that pass is fast. With a good gap sequence, shell sort beats O(n²) on many inputs while still sorting in place.
Why Faster Algorithms Use Insertion Sort for Small Inputs
Recursive algorithms such as quick sort and merge sort carry overhead for function calls and splitting. For tiny pieces, a simple loop is quicker than that overhead, even though its time grows quadratically. This is why many library sorting routines switch to an insertion-style method once a piece becomes small. The best cutoff depends on the language, the hardware and the data.
How to Test an Insertion Sort Implementation
A correct insertion sort should pass a small set of well-chosen tests. You can run all of them against the visualization above.
Edge Cases to Try
- An empty array and an array with one element.
- An already sorted array, which should take the fewest steps.
- A reverse-sorted array, which should take the most.
- An array where all values are equal.
- An array with many duplicate values, such as [3, 1, 2, 3, 1, 2].
Check Stability
Sort records such as {name, score} by score and confirm that records with equal scores keep their original order. Insertion sort with a strict greater-than test passes. Changing it to greater-or-equal breaks stability.
Compare Against a Trusted Result
Compare your output with the language’s built-in sort, and confirm the result contains exactly the same elements as the input. You can also check the swap counter: in the swap-based version shown above, the number of swaps equals the number of inversions in the input, so a reverse-sorted array of n items produces n(n − 1)/2 swaps.
Frequently Asked Questions About Insertion Sort
What is insertion sort in simple words?
It builds a sorted list one item at a time by inserting each new item into its correct place among the items before it.
Is insertion sort stable?
Yes, as long as you shift only elements that are strictly greater than the key.
Is insertion sort in place?
Yes. It needs only O(1) extra memory.
What is the best case for insertion sort?
An already sorted array. The algorithm makes n − 1 comparisons and no shifts, so it runs in O(n).
Why is insertion sort fast on nearly sorted data?
Each key only moves a short distance, so the inner loop ends quickly.
When should I use insertion sort?
Use it for small arrays, nearly sorted data, or as the small-case step inside a faster algorithm.
Is insertion sort better than bubble sort?
Usually yes. Both are O(n²) in the worst case, but insertion sort typically does fewer operations in practice.
Conclusion
Insertion sort grows a sorted section by inserting one key at a time. It is stable, in place, and very fast on nearly sorted input, but quadratic on large random data. Return to the visualization, try a sorted array and a reverse-sorted array, and compare the comparison and swap counters.