public static void qsort(int[] arr, int start, int end) {
if (end <= start) {
return;
}
int pivot = partition(arr, start, end);
qsort(arr, start, pivot - 1);
qsort(arr, pivot + 1, end);
}
private static int partition(int[] arr, int left, int right) {
for (int i = left; i < right; ++i) {
if (arr[i] < arr[right]) {
swap(arr, i, left);
++left;
}
}
swap(arr, left, right);
return left;
}
private static void swap(int[] arr, int l, int r) {
int t = arr[l];
arr[l] = arr[r];
arr[r] = t;
}