How does the recursive part of quick_sort work?
<p>Here is an implementation of quick_sort found in many places including <a href="http://en.wikipedia.org/wiki/Quicksort" rel="nofollow">wikipedia</a>.  </p>

<p>Here is my simple synopsis.</p>

<ul>
<li>Select a pivot element – ½ of left and right.</li>
<li>Start index at right and iterate left.</li>
<li>If Elements[right] &lt; P pick as flip.  </li>
<li>Start index at left and Iterate right.  </li>
<li>If Elements[left] > P pick as a flip.  </li>
<li>Flip the two elements.</li>
<li>Repeat abou the pivot point</li>
<li>Repeat recursively for each half</li>
</ul>

<p>Can someone explain the reasoning behind the two recursive lines:</p>

<pre><code>if (left &lt; j)quick_sort(arr, left, j);
if (i &lt; right)quick_sort(arr, i, right);
</code></pre>

<p>Snippet:</p>

<pre><code>  void quick_sort(int arr[], int left, int right) 
    {  
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];
    while (i &lt;= j)
      {
      while (arr[i] &lt; pivot)i++;
      while (arr[j] &gt; pivot)j--;
      if (i &lt;= j) 
        {
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
        i++;
        j--;
        }
      }
    if (left &lt; j)quick_sort(arr, left, j);
    if (i &lt; right)quick_sort(arr, i, right);
  }
</code></pre>
