Sorting

Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this Python DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.py 
arr = [5, 1, 4, 2, 8]
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(arr)

Complexity

  • Time: O(n^2) worst and average, O(n) best
  • Space: O(1)
  • Stable: yes

Implementation notes

  • Python stores arr as one list object whose slots hold references to immutable int objects. The sort mutates that same list with assignments like arr[j + 1] = arr[j]; it does not allocate a replacement list.
  • key = arr[i] binds the current integer object to a local name while larger elements shift right. The while j >= 0 and arr[j] > key guard short-circuits before any negative-index read, and the comparison uses Python integer ordering.
  • GC is not part of the visible loop behavior because the replayed work is slot reassignment inside the existing list. The trace shows each completed insert: 1 before 5, then shifting 5 for 4, then shifting 5 and 4 for 2.
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.