insertion sort in python not working
<p>I have tried the following code for insertion sort in python</p>

<pre><code>a=[int(x) for x in input().split()]
for i in range(1,len(a)):
    temp=a[i]
    for k in range (i,1,-1):
        a[k]=a[k-1]
        if a[k]&lt;temp:
            a[k]=temp
            break
print(a)
</code></pre>

<p>input: 6 4 3 2 5 8 1</p>

<p>output: [6, 4, 4, 4, 4, 5, 8]</p>

<p>It <em>does not work</em> because your implementation is faulty.<br>
When trying to shift the partially sorted list, you overwrite existing numbers by assigning <code>a[k] = a[k-1]</code> -- but where's the former value of <code>a[k]</code> then?</p>

<p>A very basic solution (yet not in-place as the original definition on a single list is defined) could look like this.</p>

<pre><code>inp = '1 4 6 3 1 6 3 5 8 1'

# 'a' is the input list
a = [int(x) for x in inp.split()]
# 'r' is the sorted list
r = []
# In the original descriptions, insertion sort operates
# on a single list while iterating over it. However, this
# may lead to major failurs, thus you better carry the
# sorted list in a separate variable if memory is not
# a limiting factor (which it can hardly be for lists that
# are typed in by the user).

for e in a:
    if not len(r):
        # The first item is the inialization
        r.append(e)
    else:
        # For each subsequent item, find the spot in 'r'
        # where it has to go.
        idx = 0
        while idx &lt; len(r) and r[idx] &lt; e: idx += 1
        # We are lazy and use insert() instead of manually
        # extending the list by 1 place and copying over
        # all subsequent items [idx:] to the right
        r.insert(idx, e)
print(r)
</code></pre>

python insertion-sort