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>The problem is with your initialization code for <code>hi</code>:</p>

<pre><code>if not hi: hi = len(arr) - 1
</code></pre>

<p>The condition <code>not hi</code> is <code>True</code> if <code>hi</code> is zero.</p>

<p>This causes <code>quicksort(arr, 0, 0)</code> and <code>quicksort(arr, 1, 0)</code> (one of which will almost always occur in the process of sorting) to try to sort most of the list again, rather than being an end to the recursion.</p>

<p>You should use the more specific test <code>if hi is None</code> instead of <code>if not hi</code>. This way you'll never incorrect reinitialize <code>hi</code> if it's zero, and the initialization code will only run if <code>hi</code> is <code>None</code> because it was not passed in to the function by the user.</p>

python sorting infinite-loop quicksort