///////    Quicksort.java    ///////

public class Quicksort
{
    public static void quicksort(int[] arr, int l, int r)
    {   if ( l >= r || l < 0 || r < 0 ) return;
        int k = partition(arr, l, r);
        quicksort(arr, l, k-1);
        quicksort(arr, k+1, r);  
    }

    private static int partition(int[] arr, int l, int r)
    {   int i=l, j=r;
        // choose middle element as pivot 
        swap(arr, (i+j)/2, r);            // pivot moved to r
        int pe = arr[r];
        while (i < j)
        {  while (i < j && arr[i] <= pe ) // from left side
              i++; 
           while (i < j && arr[j] >= pe ) // from right side
              j--;
           if (i < j) swap(arr, i++, j);  // switch elements
        }
        if (i != r) swap(arr, i, r);      // pivot element in place
        return(i);
    }

    private static void swap(int[] a, int i, int j)
    {   int tmp = a[i];
        a[i] = a [j];
        a[j] = tmp;
    }
}