title: What's wrong with this implementation of quicksort?
body: <p>I'm trying to implement the quicksort algorithm choosing the pivot as the rightmost element as described in Cormey et al., <em>Introduction to Algorithms</em>:</p>
  
  <p><a href="https://i.stack.imgur.com/Z7EIO.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Z7EIO.png" alt="enter image description here"></a></p>
  
  <p>Here is my Python implementation:</p>
  
  <pre><code>def partition(A, p, r):
      pivot = A[r]
      i = p - 1
      for j in range(p, r-1):
          if A[j] &lt; pivot:
              i += 1
              A[i], A[j] = A[j], A[i]
      A[i+1], A[r] = A[r], A[i+1]
      return i+1
  
  def quicksort(A, p, r):
      if p &lt; r:
          q = partition(A, p, r)
          quicksort(A, p, q-1)
          quicksort(A, q+1, r)
  </code></pre>
  
  <p>However, if I try to test it like so:</p>
  
  <pre><code>A = [2, 8, 7, 1, 3, 5, 6, 4]
  quicksort(A, 0, len(A)-1)
  print(A)
  </code></pre>
  
  <p>I get an array which is not sorted but just partitioned once:</p>
  
  <pre><code>[2, 3, 1, 4, 5, 7, 8, 6]
  </code></pre>
  
  <p>(That is, all the elements left (right) of the <code>4</code> are smaller (greater) than it). It seems that the recursive calls to <code>quicksort</code> are not operating in place on the input array <code>A</code> like the call to <code>partition</code>. How can I fix this?</p>