/**
 * クイックソート（再帰呼出し版）
 *
 * @version $Revision: 1.9 $, $Date: 2002/05/21 06:18:43 $
 */

public class QuickSort1 {
	/** a[] を昇順に */
	public static void sort(int a[]) {
		sort(a, 0, a.length - 1);
	}

	/** a[first..last] を昇順に */
	private static void sort(int a[], final int first, final int last) {
		final int x = a[(first + last) / 2];
		int i = first, j = last;
		for (;;) {
			while (a[i] < x)
				i++;
			while (x < a[j])
				j--;
			if (i >= j)
				break;
			int swap = a[i];
			a[i] = a[j];
			a[j] = swap;
			i++;
			j--;
		}
		if (first < i - 1)
			sort(a, first, i - 1);
		if (j + 1 < last)
			sort(a, j + 1, last);
	}

	public static void main(String[] args) {
		final int N = 10000;
		int[] a = new int[N];

		for (int i = 0; i < N; i++) {
			a[i] = (int) (Math.random() * 100);
		}

		long time = System.currentTimeMillis();
		sort(a);
		System.out.println(System.currentTimeMillis() - time);
	}
}
