title: Explanation of Hoare Partitioning algorithm
body: <p>As per the pseudo-code given in many websites, I have written this <code>Hoare</code> partitioning algorithm, which takes an array, the start and end indexes of the sub-array to be partitioned based on the pivot given. It works fine, but can somebody explain the logic, how it does what it does? Here' the code:</p>
  
  <pre><code>def hoare(arr,start,end):
       pivot = 4
       i,j = start,end
       while i &lt; j:
          while i &lt; j and arr[i] &lt;= pivot:
              i += 1
          while j &gt;= i and arr[j] &gt; pivot:
              j -= 1
          if i &lt; j:
              arr[i],arr[j] = arr[j],arr[i]
       return j    
  </code></pre>
  
  <p>There's another variant of the partitioning, the <code>Lomuto</code> algorithm. It does something similar, although since I don't understand the <code>Hoare</code> algorithm in the first place, I can't spot the difference. Can anybody explain what's going on in the algorithm, and which one gives a better performance in which case?</p>