AlgoViz

Back to All Algorithms
Insertion Sort
Category: Sorting | Time: O(n^2) | Space: O(1)
Visualization
Visual representation of the data structure
About Insertion Sort

A simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it provides several advantages: simple implementation, efficient for (quite) small data sets, adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position, and stable (i.e., does not change the relative order of elements with equal keys).

Code Editor
The code is for reference. Editing it won't affect the visualization.
1
2
3
4
5
6
7
8
9
10
11
12
13
Variable State
{
  "arr": "[12, 11, 13, 5, 6]",
  "n": 5
}
Insertion Sort: How It Works
Last updated October 28, 2026

Overview

Insertion Sort builds the sorted result one element at a time, the way most people sort a hand of playing cards. It takes the next element (the key), shifts every larger element in the sorted prefix one slot to the right, and drops the key into the gap that opens up.

Because elements are shifted rather than swapped, each step writes only once per moved element. On data that is already nearly sorted, the inner loop stops almost immediately, which is why Insertion Sort is the fastest simple sort in practice and is used inside Tim Sort and Intro Sort for small pieces.

With the default input 12, 11, 13, 5, 6, notice how 5 has to travel all the way to the front, shifting 13, 12 and 11, while 13 does not move at all.

Step by step

  1. Treat arr[0] as a sorted prefix of length 1.
  2. Take key = arr[i] for the next index i.
  3. Walk j left from i - 1 while arr[j] > key, copying arr[j] into arr[j + 1].
  4. Write key into arr[j + 1], the first position where it is not smaller than its left neighbour.
  5. Repeat for every i up to n - 1.

Complexity

CaseCostWhy
Best caseO(n)Already-sorted input: every inner loop stops after one comparison.
Average caseO(n^2)Each key moves about halfway back through the prefix.
Worst caseO(n^2)Reverse-sorted input shifts every key to the front.
Extra spaceO(1)Only the key variable is needed.

When to use it

  • Small arrays (roughly under 16–32 elements), where its low overhead beats O(n log n) algorithms.
  • Nearly sorted data, or data that arrives one item at a time and must stay sorted (online sorting).
  • As the finishing step inside hybrid sorts such as Tim Sort and Intro Sort.

Common mistakes

  • Using >= in the while condition shifts equal elements and breaks stability.
  • Swapping on every step instead of shifting triples the number of writes for no benefit.
  • Forgetting the j >= 0 bound, which reads arr[-1] when the key is the smallest so far.
Worked Example: Insertion Sort Dry Run
Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Insertion Sort: follow each row, predict the next one, and compare. The run below takes 43 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input
12, 11, 13, 5, 6
Result
arr = [5, 6, 11, 12, 13], return value = [5, 6, 11, 12, 13]
StepLineArrayWhat happens
12[12, 11, 13, 5, 6]n = 5
56[12, 11, 13, 5, 6]n = 5, i = 1, key = 11, j = 0, condition = 0 >= 0 && 12 > 11
67[12, 12, 13, 5, 6]n = 5, i = 1, key = 11, j = 0, arr[j+1] = 12
86[12, 12, 13, 5, 6]n = 5, i = 1, key = 11, j = -1, condition = false
910[11, 12, 13, 5, 6]n = 5, i = 1, key = 11, j = -1, arr[j+1] = 11
136[11, 12, 13, 5, 6]n = 5, i = 2, key = 13, j = 1, condition = 1 >= 0 && 12 > 13
186[11, 12, 13, 5, 6]n = 5, i = 3, key = 5, j = 2, condition = 2 >= 0 && 13 > 5
197[11, 12, 13, 13, 6]n = 5, i = 3, key = 5, j = 2, arr[j+1] = 13
216[11, 12, 13, 13, 6]n = 5, i = 3, key = 5, j = 1, condition = 1 >= 0 && 12 > 5
227[11, 12, 12, 13, 6]n = 5, i = 3, key = 5, j = 1, arr[j+1] = 12
246[11, 12, 12, 13, 6]n = 5, i = 3, key = 5, j = 0, condition = 0 >= 0 && 11 > 5
257[11, 11, 12, 13, 6]n = 5, i = 3, key = 5, j = 0, arr[j+1] = 11
276[11, 11, 12, 13, 6]n = 5, i = 3, key = 5, j = -1, condition = false
2810[5, 11, 12, 13, 6]n = 5, i = 3, key = 5, j = -1, arr[j+1] = 5
326[5, 11, 12, 13, 6]n = 5, i = 4, key = 6, j = 3, condition = 3 >= 0 && 13 > 6
337[5, 11, 12, 13, 13]n = 5, i = 4, key = 6, j = 3, arr[j+1] = 13
356[5, 11, 12, 13, 13]n = 5, i = 4, key = 6, j = 2, condition = 2 >= 0 && 12 > 6
367[5, 11, 12, 12, 13]n = 5, i = 4, key = 6, j = 2, arr[j+1] = 12
386[5, 11, 12, 12, 13]n = 5, i = 4, key = 6, j = 1, condition = 1 >= 0 && 11 > 6
397[5, 11, 11, 12, 13]n = 5, i = 4, key = 6, j = 1, arr[j+1] = 11
416[5, 11, 11, 12, 13]n = 5, i = 4, key = 6, j = 0, condition = 0 >= 0 && 5 > 6
4210[5, 6, 11, 12, 13]n = 5, i = 4, key = 6, j = 0, arr[j+1] = 6
4312[5, 6, 11, 12, 13]return value = [5, 6, 11, 12, 13]
Frequently Asked Questions
About Insertion Sort

What is Insertion Sort?

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It iterates through an input array and for each element, it finds its correct position in the already-sorted part of the array and inserts it there.

What is the time complexity of Insertion Sort?

The worst-case and average-case time complexity is O(n^2). However, its best-case time complexity, when the array is already sorted, is O(n), making it very efficient for nearly-sorted data.

Is Insertion Sort an in-place, stable algorithm?

Yes, Insertion Sort is both an in-place algorithm (requiring only O(1) additional memory) and a stable sorting algorithm (it preserves the relative order of equal elements).

Why is Insertion Sort considered an 'online' algorithm?

An online algorithm can process its input piece-by-piece in a serial fashion. Insertion sort can sort a list as it receives it, making it suitable for situations where data arrives over time.

How does Insertion Sort's performance compare to more advanced algorithms like Quick Sort?

For large, random datasets, Insertion Sort is significantly slower due to its O(n^2) complexity. However, for small arrays, its low overhead makes it faster. This is why hybrid algorithms like Tim Sort and IntroSort use it for small partitions.

What is a binary Insertion Sort?

A binary Insertion Sort is an optimization where binary search is used to find the correct position to insert the current element in the sorted part of the array. This reduces the number of comparisons from O(n) to O(log n) per insertion, but the number of swaps remains O(n) in the worst case, so the overall complexity is still O(n^2).

When would you choose Insertion Sort over Bubble Sort?

Almost always. Insertion Sort is generally more efficient than Bubble Sort. It performs fewer comparisons on average and is particularly fast on data that is already substantially sorted.

Can you describe the movement of data in Insertion Sort?

The algorithm maintains a sorted sub-array at the beginning. It takes the first element of the unsorted part and 'inserts' it into the sorted sub-array by shifting all larger elements one position to the right until the correct spot is found.

Is Insertion Sort a divide-and-conquer algorithm?

No, it is not. It uses an incremental approach, building up a sorted list one element at a time, rather than dividing the problem into smaller subproblems like Merge Sort or Quick Sort.

How does Insertion Sort handle duplicate keys?

As a stable sort, if it encounters an element that is equal to one already in the sorted portion, it will insert the new element after the existing one, preserving their original order.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.
Related Interview Questions
Practice with real problems

Merge Sorted Arrays

From: Meta

View Question