DSA Insertion Sort

How it works

This approach adapts well to small or nearly ordered inputs because an item close to its final position requires few shifts. The comparison uses strictly greater rather than greater-or-equal, preserving the original order among equal keys. The implementation copies the input once and then performs its shifts inside that copy. A linked-list insertion has a different movement and lookup cost, so do not transfer this exact bound blindly to another representation.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as insertion-sort.py and run python insertion-sort.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def insertion_sort(values, key=lambda item: item):
    result = list(values)
    for right in range(1, len(result)):
        item = result[right]
        left = right - 1
        while left >= 0 and key(result[left]) > key(item):
            result[left + 1] = result[left]
            left -= 1
        result[left + 1] = item
    return result

print(insertion_sort([14, 5, 11, 5, 2]))
print(insertion_sort([]))

Expected result

[2, 5, 5, 11, 14]
[]

The loop maintains an ordered prefix and accepts an empty sequence naturally. The item held in a local variable is not lost while earlier entries shift right. Boundary tests check duplicates, negative values and the original input’s unchanged state.

Time, space and assumptions

This version is O(n²) worst-case and O(n) best-case on already ordered input. Its copy uses O(n) output storage; the shifting work uses O(1) additional state.