DSA — Sorting Algorithms

Insertion Sort

Build sorted array one element at a time. Pick each element and slide it into the correct position.

— min read
O(n²)Time Avg
O(n)Best Case
O(1)Space
StableSort
Best forSmall n
// INSERTION SORT — LIVE ANIMATION
Speed
Press ▶ Sort to begin
How It Works
Python Code
Complexity
Quiz
Practice
01
Pick Key
Take the next element from the unsorted portion.
key = arr[i]
02
Shift Larger Elements
Slide sorted elements right to make room.
arr[j+1] = arr[j]
03
Insert Key
Place key in correct sorted position.
arr[j+1] = key
04
Online Algorithm
Works on live streaming data — no need to see all elements first.
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]; j -= 1
        arr[j+1] = key
O(n)
Best Case
Already sorted — 1 comparison per element
O(n²)
Worst Case
Reverse sorted
Adaptive
Nearly Sorted
Fastest simple sort for nearly sorted data
Stable
Equal elements
Preserves relative order
Insertion Sort is most efficient when the input is:
Progress 0 / 5 solved
5 problems · 3 PBC · 2 Startup
#148 Insertion Sort List Amazon, Microsoft PBC →
#148 Sort List Google, Meta PBC →
#INV Count Inversions Google, Amazon PBC →
#35 Binary Search Insertion Point Zomato STARTUP →
#274 H-Index Freshworks STARTUP →
← Selection Sort