Quicksort: Infinite Loop
<p>The following implementation of <code>QuickSort</code> runs into infinite loop</p>

<pre class="lang-py prettyprint-override"><code>def partition(arr, lo, hi):
    pivot = lo
    for i in range(lo+1, hi+1):
        if arr[i] &lt;= arr[lo]:
            pivot += 1
            arr[i], arr[pivot] = arr[pivot], arr[i]
    arr[lo], arr[pivot] = arr[pivot], arr[lo]
    return pivot

def quickSort(arr, lo=0, hi=None):
    if not hi: hi = len(arr) - 1
    if lo &gt;= hi: return

    pivot = partition(arr, lo, hi)
    quickSort(arr, lo, pivot-1)
    quickSort(arr, pivot+1, hi)


arr = [5,3,2,-9,1,6,0,-1,9,6,2,5]
quickSort(arr)
print(arr)
</code></pre>

<p>I presume the <code>partition</code> function is the culprit. Not able to figure out the mistake. </p>

<p>Thanks</p>

<p>At one point, your loop never works in partition def. See below</p>

<pre><code>[5, 3, 2, -9, 1, 6, 0, -1, 9, 6, 2, 5]
lo 0 hi 11
pivot 8
[5, 3, 2, -9, 1, 0, -1, 2, 5, 6, 6, 9]
lo 0 hi 7
pivot 7
[2, 3, 2, -9, 1, 0, -1, 5, 5, 6, 6, 9]
lo 0 hi 6
pivot 5
[-1, 2, -9, 1, 0, 2, 3, 5, 5, 6, 6, 9]
lo 0 hi 4
pivot 1
[-9, -1, 2, 1, 0, 2, 3, 5, 5, 6, 6, 9]
lo 0 hi 11
pivot 0
[-9, -1, 2, 1, 0, 2, 3, 5, 5, 6, 6, 9]
lo 1 hi 11
</code></pre>

<p>partition doesn't seem to be doing the entire job and correctly, it is a two step process. See a sample partition def below. Also, you can refer to original source <a href="http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html" rel="nofollow">here</a>:    </p>

<pre><code> def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark &lt;= rightmark and alist[leftmark] &lt;= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] &gt;= pivotvalue and rightmark &gt;= leftmark:
           rightmark = rightmark -1

       if rightmark &lt; leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark
</code></pre>

python sorting infinite-loop quicksort