partition.java

private static int partition(int[] arr, int first, int last) {
    int pivot = arr[(first + last)/2];
    int i = first - 1;  // index going left to right
    int j = last + 1;   // index going right to left
    
    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);
        do {
            j--;
        } while (arr[j] > pivot); 
        
        if (i < j)
            Sort.swap(arr, i, j);
        else
            return j;   // index of last element in the left subarray
    }
}