Insertion Sort — Practice Tasks¶

def insertion_sort(arr):
    # TODO
    pass

def insertion_sort_desc(arr):
    # TODO: change > to <
    pass

def insertion_sort_strings(arr):
    # TODO
    pass

def insertion_sort_by(arr, key=lambda x: x):
    # TODO
    pass

def online_insert(sorted_arr, x):
    # TODO
    pass

import bisect
def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        # TODO: find position via bisect_left, then shift+insert
        pass

def shell_sort(arr):
    n = len(arr); gap = n // 2
    while gap > 0:
        # TODO: gapped insertion
        gap //= 2

CUTOFF = 16
def hybrid_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if hi - lo <= CUTOFF:
        # TODO: insertion sort range
        return
    # TODO: split, recurse, merge

def count_inversions(arr):
    # TODO: use insertion-shift count
    return 0

class Node:
    def __init__(self, val, nxt=None):
        self.val = val; self.next = nxt

def insertion_sort_linked(head):
    # TODO: build sorted list by inserting each node
    return head

def top_k_stream(stream, k):
    sorted_top = []
    for x in stream:
        # TODO: insert if smaller than max; keep size ≤ k
        yield list(sorted_top)

def insertion_sort_sentinel(arr):
    # Place arr[0] = -infinity to skip bound check
    arr.insert(0, float('-inf'))
    # TODO
    arr.pop(0)

import time, random
def benchmark():
    n = 10000
    sorted_data = list(range(n))
    random_data = random.sample(range(n), n)
    nearly = list(range(n))
    for _ in range(50): # 0.5% perturbation
        i, j = random.randint(0,n-1), random.randint(0,n-1)
        nearly[i], nearly[j] = nearly[j], nearly[i]
    for label, data in [("sorted",sorted_data),("nearly",nearly),("random",random_data)]:
        t = time.perf_counter()
        insertion_sort(list(data))
        print(f"{label}: {time.perf_counter()-t:.3f}s")

def find_run(arr, lo):
    # TODO: find max j such that arr[lo..j] is monotonic
    return lo
def extend_run(arr, lo, hi, target_len):
    # TODO: extend run to target_len using insertion sort
    pass