Insertion Sort — Find the Bug¶

while j >= 0 and arr[j] >= x:  # BUG

def insertion_sort(arr):
    for i in range(1, len(arr)):
        j = i - 1
        while j >= 0 and arr[j] > arr[i]:  # BUG: arr[i] gets overwritten
            arr[j+1] = arr[j]; j -= 1
        arr[j+1] = arr[i]  # arr[i] is now wrong

arr[j] = arr[j-1]  # BUG: should be arr[j+1] = arr[j]

for i in range(0, len(arr)):  # BUG: should start at 1
    x = arr[i]; j = i - 1  # j = -1 → no shift, ok... but useless work
    while j >= 0 and arr[j] > x: ...

while arr[j] > x:  # BUG: no bound check
    arr[j+1] = arr[j]; j -= 1

while j >= 0 and arr[j] < x:  # BUG: should be >

while j >= 0 and arr[j] > arr[j+1]:
    arr[j], arr[j+1] = arr[j+1], arr[j]
    j -= 1

while j >= 0 and arr[j] > x:
    arr[j+1] = arr[j]
    # BUG: forgot j -= 1 → infinite loop
arr[j+1] = x

import math
data = [3.0, math.nan, 1.0]
insertion_sort(data)  # NaN comparisons all return False

def linked_insert(head, new_node):
    # ... insert new_node somewhere
    # BUG: didn't update the previous node's .next

def online_insert(arr, x):
    arr.append(0)
    i = len(arr) - 2
    while arr[i] > x:  # BUG: when arr was empty, i = -1, IndexError
        arr[i+1] = arr[i]; i -= 1