My version of the quicksort algorithm from Wikipedia does not work
<pre><code>def partition(A,lo,hi):
    pivot = A[hi]
    i=lo
    #Swap
    for j in range(lo,hi-1):
        if (A[j] &lt;= pivot):
            val=A[i]
            A[i]=A[j]
            A[j]=val
            i=i+1
        val=A[i]
        A[i]=A[hi]
        A[hi]=val
    return(i)

def quicksort(A,lo,hi):
  if (lo&lt;hi):
      p=partition(A,lo,hi)
      quicksort(A,lo,p-1)
      quicksort(A,p+1,hi)
      return(A)
</code></pre>

<p>If my input is <code>[5,3,2,6,8,9,1]</code> the output is <code>[1, 2, 5, 3, 8, 9, 6]</code>, why is that?</p>

<pre><code>def partition(A,lo,hi):
    pivot = A[hi]
    i=lo
#Swap
    for j in range(lo,hi-1):
        if (A[j] &lt;= pivot):
            val=A[i]
            A[i]=A[j]
            A[j]=val
            i=i+1
    val=A[i]       #was in for loop was suppose to be outside of for loop
    A[i]=A[hi]     #was in for loop was suppose to be outside of for loop
    A[hi]=val      #was in for loop was suppose to be outside of for loop
    return(i)

def quicksort(A,lo,hi):
  if (lo&lt;hi):
      p=partition(A,lo,hi)
      quicksort(A,lo,p-1)
      quicksort(A,p+1,hi)
      return(A)

x = [5,3,2,6,8,9,1]
print(quicksort(x,0,len(x)-1))
</code></pre>

<p>Simple fix, your indentation was wrong in partition.</p>

<p>Outputs </p>

<pre><code>[1, 2, 3, 5, 6, 8, 9]
</code></pre>

python quicksort