Sorting Algorithms

Insertion Sort

● Beginner ⏱ 6 min read sorting

Insertion sort builds a sorted subarray one element at a time, like sorting a hand of playing cards. Each new element is inserted into its correct position among the already-sorted elements by shifting larger values rightward.

How It Works

Think of sorting playing cards in your hand. You pick up one card at a time and slide it left until it is in the right place among the cards you already hold.

Text

Array: [5, 3, 8, 1, 2]

i=1: key=3, compare with 5 → shift 5 right → [5,5,8,1,2] → insert 3 → [3,5,8,1,2]
i=2: key=8, compare with 5 → 8>5, stop → [3,5,8,1,2]
i=3: key=1, shift 8,5,3 right → [3,3,5,8,2] → ... → [1,3,5,8,2] → insert 1 → [1,3,5,8,2]
     (actually: [1,3,5,8,2] after inserting at front)
i=4: key=2, shift 8,5,3 right → insert 2 → [1,2,3,5,8]

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 element right
            j -= 1
        arr[j + 1] = key          # insert key in its correct position
    return arr

nums = [5, 3, 8, 1, 2]
print(insertion_sort(nums))   # [1, 2, 3, 5, 8]

# Nearly-sorted input — only a few shifts needed
nearly_sorted = [1, 2, 3, 5, 4]
print(insertion_sort(nearly_sorted))   # [1, 2, 3, 4, 5] — O(n) work

Step-by-step Trace

Python

def insertion_sort_verbose(arr):
    arr = 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(f"i={i}, key={key}: {arr}")
    return arr

insertion_sort_verbose([5, 3, 8, 1, 2])
# i=1, key=3: [3, 5, 8, 1, 2]
# i=2, key=8: [3, 5, 8, 1, 2]
# i=3, key=1: [1, 3, 5, 8, 2]
# i=4, key=2: [1, 2, 3, 5, 8]

Why Python Uses Timsort

Python’s sorted() and list.sort() use Timsort — a hybrid algorithm that combines merge sort with insertion sort. Timsort uses insertion sort for small “runs” (typically 32–64 elements) because insertion sort is faster than merge sort at small sizes due to lower overhead. It then uses merge sort to combine the sorted runs.

Python

# Python's built-in sort is Timsort — O(n log n) and stable
data = [5, 3, 8, 1, 2]
print(sorted(data))       # [1, 2, 3, 5, 8]  — returns new list
data.sort()               # sorts in-place, returns None
print(data)               # [1, 2, 3, 5, 8]

# Custom key function
words = ["banana", "apple", "cherry", "date"]
print(sorted(words, key=len))   # ['date', 'apple', 'banana', 'cherry']

# Reverse sort
print(sorted([3, 1, 4, 1, 5], reverse=True))  # [5, 4, 3, 1, 1]

💡

Insertion sort shines on small or nearly-sorted data

For n < 32 elements, insertion sort is often faster than merge sort in practice. And if the input is already 90% sorted (few inversions), insertion sort runs close to O(n) — far fewer operations than the O(n log n) of merge sort on the same input.

Complexity Table

Case	Time	Space	Note
Best case	O(n)	O(1)	Already sorted; inner loop never executes
Average case	O(n²)	O(1)
Worst case	O(n²)	O(1)	Reverse-sorted; every element shifts to front
Stable	Yes	—	Equal elements preserve original order
Adaptive	Yes	—	Faster on nearly-sorted input