Quicksort with insertion sort Python not working
<p>I've been trying to run the quicksort with a switch to insertion sort when the sub array size is less than 10. So it turns out, i'm not getting a sorted list.</p>

<p>Where am i going wrong?</p>

<pre><code>import random
import time

m = 0

def quicksort(numList, first, last):
    if first&lt;last:
        sizeArr = last - first + 1
        if(sizeArr &lt; m):
            insert_sort(numList, first, last)
        else:
            mid = partition(numList, first, last)
            quicksort(numList, first, mid-1)
            quicksort(numList, mid + 1, last)

def partition(numList, first, last):
    piv = numList[last]
    i = first-1
    for j in range(first,last):
        if numList[j] &lt; piv:
            i += 1
            temp = numList[i]
            numList[i] = numList[j]
            numList[j] = temp

    tempo = numList[i+1]
    numList[i+1] = numList[last]
    numList[last] = tempo

    return i+1

def insert_sort(numList, first, last):
    for x in range(first, last):
        key = numList[x]
        y = x-1
        while y &gt; -1 and numList[y]&gt; key:
            numList[y+1] = numList[y]
            y = y-1
        numList[y+1] = key

if __name__ == '__main__':
    start = time.time()
    numList = random.sample(range(5000), 100)
    m = 10
    quicksort(numList, 0, len(numList) - 1)
    print numList
    print "Time taken: " + str(time.time() - start)
</code></pre>

<p>input is some random array of sizes between 100 - 1000000. I'm using a random generator as you can see. </p>

<p>Please help me.</p>

<p>You have an off-by-one error in <code>insert_sort</code> function. Iterate over <code>range(first, last+1)</code> and it will sort correctly.</p>

python quicksort insertion-sort