Insertion sort

Like sorting a hand of cards: take the next card and slide it left past every larger card.

def insertion_sort(nums):
    for i in range(1, len(nums)):
        current = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > current:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = current
    return nums

Everything left of i is always sorted. Each new item shifts larger items right until it finds its place. The worst case is O(n²), but on nearly sorted data it is close to O(n), and it is stable. Python's built-in sort (Timsort) uses insertion sort for short runs for exactly that reason.