How does Python insertion sort work?

Question

Here's a Python implementation of insertion sort, I tried to follow the values on paper but once the counting variable i gets bigger than len(s) I don't know what to do, how/why does it still run?

def sort_numbers(s):
    for i in range(1, len(s)):
        val = s[i]
        j = i - 1
        while (j >= 0) and (s[j] > val):
            s[j+1] = s[j]
            j = j - 1
        s[j+1] = val

def main():
    x = eval(input("Enter numbers to be sorted: "))
    x = list(x)
    sort_numbers(x)
    print(x)

Answer 1

Or, this one:

def ins_sort(k):
    for i in range(1,len(k)):    #since we want to swap an item with previous one, we start from 1
        j = i                    #create i's copy (or not)
        temp = k[j]              #temp will be used for comparison with previous items, and sent to the place it belongs
        while j > 0 and temp < k[j-1]: #j>0 bcoz no point going till k[0] since there is no seat available on its left, for temp
            k[j] = k[j-1] #Move the bigger item 1 step right to make room for temp
            j=j-1 #take k[j] all the way left to the place where it has a smaller/no value to its left.
        k[j] = temp
    return k

Answer 2

Consider [3, 2, 1]

The loop starts with 3. Since it is the first item in the list there is nothing else to do.

[3, 2, 1]

The next item is 2. It compares 2 to 3 and since 2 is less than 3 it swaps them, first putting 3 in the second position and then placing 2 in the first position.

[2, 3, 1]

The last item is 1. Since 1 is less than 3 it moves 3 over.

[2, 3, 3]

Since 1 is less than 2 it swaps moves 2 over.

[2, 2, 3]

Then it inserts 1 at the beginning.

[1, 2, 3]

Answer 3

To see how that implementation works, check it out visualized here: http://goo.gl/piDCnm

However, here is a less confusing implementation of insertion sort:

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

Answer 4

a recursive implementation

def insert(x, L):
    if [] == L:      return [x]
    elif x <= L[0]:  return [x] + L
    else:            return [L[0]] + insert(x,L[1:])

def insertion_sort(L):
    if [] == L:  return []
    else:        return insert(L[0], insertion_sort(L[1:]))

# test
import random

L = [random.randint(1,50) for _ in range(10)]

print L
print insertion_sort(L)