public class QSortXAlgorithm extends SortAlgorithm {

void sort(int[] a) throws Exception {
	sort(a,0,a.length-1);
}

void sort(int[] a, int l, int r) throws Exception {
	pause(l,r);
	if (r <= l) return;
	int i = l-1, j = r;
	int p = l-1, q = r;

	while(true) {
	while (a[++i]<a[r]);
	while (a[r]<a[--j]) if (j == l) break;
	if (i >= j) break;
	exch(a, i, j);

	if (a[i]==a[r]) exch(a,++p, i);
	if (a[j]==a[r]) exch(a,--q, j);
	}
	exch(a, i, r);
	j = i - 1;
	i = i + 1;
	for (int k = l ; k <= p; k++) exch(a, k, j--);
	for (int k = r-1; k >= q; k--) exch(a, k, i++);
	sort(a, l, j);
	sort(a, i, r);
}

void exch(int[] a, int i, int j) throws Exception {
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
	pause();
}

}