title: Inplace Quicksort in Java
body: <p>For refreshing some Java I tried to implement a quicksort (inplace) algorithm that can sort integer arrays. Following is the code I've got so far. You can call it by <code>sort(a,0,a.length-1)</code>.</p>
  
  <p>This code obviously fails (gets into an infinite loop) if both 'pointers' <code>i,j</code> point each to an array entry that have the same values as the pivot. The pivot element <code>v</code> is always the right most of the current partition (the one with the greatest index).</p>
  
  <p>But I just cannot figure out how to avoid that, does anyone see a solution?</p>
  
  <pre><code>static void sort(int a[], int left, int right)   {
      if (right &gt; left){
          int i=left, j=right-1, tmp;
          int v = a[right]; //pivot
          int counter = 0;
          do {
              while(a[i]&lt;v)i++;
              while(j&gt;0 &amp;&amp; a[j]&gt;v)j--;
  
              if( i &lt; j){
                  tmp = a[i];
                  a[i] = a[j];
                  a[j] = tmp;
              }
          } while(i &lt; j);
          tmp = a[right];
          a[right] = a[i];
          a[i] = tmp;
          sort(a,left,i-1);
          sort(a,i+1,right);
  
      }
  }    
  </code></pre>