title: Quicksort Hoare's partition
body: <pre><code>algorithm quicksort(A, lo, hi) is
      if lo &lt; hi then
          p := partition(A, lo, hi)
          quicksort(A, lo, p)
          quicksort(A, p + 1, hi)
  
  algorithm partition(A, lo, hi) is
      pivot := A[⌊(hi + lo) / 2⌋]
      i := lo - 1
      j := hi + 1
      loop forever
          do
              i := i + 1
          while A[i] &lt; pivot
          do
              j := j - 1
          while A[j] &gt; pivot
          if i ≥ j then
              return j
          swap A[i] with A[j]
  </code></pre>
  <p>I tried to find explicit answers to the following questions in <a href="https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme" rel="nofollow noreferrer">Quicksort/Hoare_partition_scheme</a> but I could not, although trying out some examples by hand shows that the following would most likely be correct...
  My questions are, is it always guaranteed that</p>
  <ul>
  <li><code>partition</code> returns the position of the chosen pivot</li>
  <li>does it matter to return <code>i</code> or <code>j</code>, or rather would it not be the case that the algorithm stops at  <code>i==j</code></li>
  <li>in the <code>quicksort</code> does it matter if the calls are <code>(lo,p-1) and (p,hi)</code> vs <code>(lo,p) and (p+1,hi)</code></li>
  </ul>