Insertion Sort

DSA · Sorting Algorithms

Theory

Insertion sort builds the sorted list one element at a time, like sorting playing cards in your hand. Each new element is shifted left past larger elements until it reaches its correct place. It runs in O(n) on nearly sorted data and O(n²) in the worst case, and it is stable and in place.

Why we use it

It is very fast for small or almost-sorted inputs, which is why real sort implementations (like Timsort) use it for small runs.

When to use it

Use it for small arrays, nearly sorted data, or when items arrive one by one and must stay sorted.

How it works

  1. Start: i = 1
  2. key = arr[i], j = i - 1
  3. j >= 0 and arr[j] > key? Yes: Shift arr[j] right, j = j - 1, check again. No: Place key at arr[j+1].
  4. i < n - 1? Yes: i = i + 1, repeat. No: Array is sorted.
  5. Done

Syntax

for i in 1..n-1:
    key = arr[i]; j = i-1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]; j -= 1
    arr[j+1] = key

Time: O(n²) worst, O(n) best   Space: O(1)   Stable

Example

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
        print("Inserted", key, "->", arr)
    return arr

insertion_sort([12, 11, 13, 5, 6])

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic