Insertion sort doesn't sort
<p>I have attempted to create an insertion sort in python, however the list returned is not sorted. What is the problem with my code?</p>

<p>Argument given: [3, 2, 1, 4, 5, 8, 7, 9, 6]</p>

<p>Result: 2
1
3
6
4
7
5
8
9</p>

<p>Python code:</p>

<pre><code>def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        posfound = 0 #defaults to 0
        for j in range(len(sorted_list)):
            if sorted_list[j] &gt; i:
                sorted_list.insert(j-1, i) #put the number in before element 'j'
                posfound = 1 #if you found the correct position in the list set to 1
                break
        if posfound == 0: #if you can't find a place in the list
            sorted_list.insert(len(sorted_list), i) #put number at the end of the list
    return sorted_list
</code></pre>

<p>As Efferalgan &amp; tzaman have mentioned your core problem is due to an off-by-one error. To catch these sorts of errors it's useful to print <code>i</code>, <code>j</code> and <code>sorted_list</code> on each loop iteration to make sure they contain what you think they contain.</p>

<p>Here are a few versions of your algorithm. First, a repaired version of your code that fixes the off-by-one error; it also implements Efferalgan's suggestion of using <code>.append</code> if an insertion position isn't found.</p>

<pre><code>def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        posfound = 0 #defaults to 0
        for j in range(len(sorted_list)):
            if sorted_list[j] &gt; i:
                sorted_list.insert(j, i) #put the number in before element 'j'
                posfound = 1 #if you found the correct position in the list set to 1
                break
        if posfound == 0: #if you can't find a place in the list
            sorted_list.append(i) #put number at the end of the list
    return sorted_list
</code></pre>

<p>Here's a slightly improved version that uses an <code>else</code> clause on the loop instead of the <code>posfound</code> flag; it also uses slice assignment to do the insertion.</p>

<pre><code>def insertion_sort(mylist):
    sorted_list = []
    for i in mylist:
        for j in range(len(sorted_list)):
            if sorted_list[j] &gt; i:
                sorted_list[j:j] = [i]
                break
        else: #if you can't find a place in the list
            sorted_list.append(i) #put number at the end of the list
    return sorted_list
</code></pre>

<p>Finally, a version that uses <code>enumerate</code> to get the indices and items in <code>sorted_list</code> rather than a simple <code>range</code> loop.</p>

<pre><code>def insertion_sort(mylist):
    sorted_list = []
    for u in mylist:
        for j, v in enumerate(sorted_list):
            if v &gt; u:
                sorted_list[j:j] = [u]
                break
        else: #if you can't find a place in the list
            sorted_list.append(u) #put number at the end of the list
    return sorted_list
</code></pre>

python algorithm insertion-sort