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>You need to change <code>sorted_list.insert(j-1, i)</code> to be  <code>sorted_list.insert(j, i)</code> to insert before position <code>j</code>. </p>

<p><code>insert(j-1, ..)</code> will insert before the <em>previous</em> element, and in the case where <code>j=0</code> it'll wrap around and insert before the last element. </p>

<p>The <a href="https://docs.python.org/3/tutorial/datastructures.html#data-structures" rel="nofollow">Python data structures tutorial</a> may be useful. </p>

python algorithm insertion-sort