Insertion Sort Algorithm

The insertion sort algorithm builds a sorted list one item at a time, sliding each new number left until it sits in the right place, much like sorting a hand of playing cards. It is the fastest simple sort on small or nearly sorted lists. Step through it below, then read how it works.

What is Insertion Sort?

Insertion Sort builds the sorted list one element at a time. It takes the next element from the unsorted part and inserts it into its correct position in the sorted part, much like sorting playing cards in your hand.

Key insight: Start with one element (trivially sorted), then insert each following element into the right place. The closer the list is to sorted, the fewer moves are needed, which is why it is fast on nearly sorted data.

Insertion Sort Time Complexity

Measure	Value
Best case	O(n)
Average case	O(n²)
Worst case	O(n²)
Space	O(1)
Stable	Yes

For a formal definition and complexity analysis, see the NIST Dictionary of Algorithms and Data Structures entry for insertion sort.

Algorithm Steps

1. Start with the second element as the current key.
2. Compare the key with the elements to its left in the sorted part.
3. Shift every larger element one position to the right.
4. Insert the key into the gap.
5. Move to the next element and repeat until the list is sorted.

Advantages and Disadvantages

Advantages

• Adaptive: O(n) on nearly sorted data
• Stable: preserves the order of equal elements
• Online: can sort items as they arrive
• In place with O(1) extra memory
• Very low overhead, so it is fast on small lists

Disadvantages

• O(n²) time on random or reverse-sorted data
• Many element shifts on large lists
• Not suitable as the main sort for big inputs

Real-World Applications

• Nearly sorted data: excellent performance on partially sorted arrays
• Online sorting: can sort data as it arrives (streaming)
• Small datasets, and as the base case in hybrid algorithms
• Part of Timsort and other advanced algorithms

When to Use Insertion Sort

Use it for small lists, nearly sorted data or as the finishing step in a hybrid sort. For large random data, use Merge, Quick or Heap Sort.

Insertion Sort Implementation

Python

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]        # shift larger element right
            j -= 1
        arr[j + 1] = key               # insert key
    return arr

JavaScript

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];             // shift larger element right
      j--;
    }
    arr[j + 1] = key;                  // insert key
  }
  return arr;
}

FAQ

Why is insertion sort fast on nearly sorted data?

Each element only moves left past the elements that are out of order with it. If the list is already almost sorted, each new element moves only a step or two, so the total work is close to O(n).

Is insertion sort stable?

Yes. An element only moves left past strictly larger values, so equal elements keep their original order.

Is insertion sort used in real libraries?

Yes, inside hybrid sorts. Timsort uses insertion sort to sort short runs before merging them, and many quicksort-based library sorts switch to insertion sort for very small partitions because it has little overhead.

---

More Sorting Algorithms

• Bubble Sort
• Selection Sort
• Shell Sort
• Timsort