public class QuickSort {
	private static void sort(int[] ns, int lower, int upper) {
		if (lower < upper) {
			int l = lower;
			int u = upper - 1;
			int middle = Math.floorDiv(lower + upper, 2);
			while (l <= u) {
				while (ns[l] < ns[middle]) {
					l++;
				}
				while (ns[middle] < ns[u]) {
					u--;
				}
				if (l < u) {
					int tmp = ns[l];
					ns[l] = ns[u];
					ns[u] = tmp;
				}
			}
			sort(ns, lower, middle + 1);
			sort(ns, middle, upper);
		}
	}

	public static void qsort(int[] ns) {
		sort(ns, 0, ns.length);
	}
}