TestPaste

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // take the first element as the pivot
         int i = low;
         int j = high + 1;
         while (true) {
           while (arr[++i] <= pivot) {
             if (i == high) break;
           }

           while (arr[--j] >= pivot) {
             if (j == low) break;
           }

           if (j <= i) break;
           int tmp = arr[i];
           arr[i] = arr[j];
           arr[j] = tmp;
         }
         arr[low] = arr[j];
         arr[j] = pivot;

        return j;
    }