public class SortTesting {

	public static void main(String[] args) {
		int length = 10000;
		int[] list = new int[length];
		for (int i = 0; i < length; i++)
			list[i] = (int) (100 * Math.random());
		long start = System.currentTimeMillis();
		selectSort(list);
		System.out.println(System.currentTimeMillis() - start);
		start = System.currentTimeMillis();
		sort(list);
		System.out.println(System.currentTimeMillis() - start);
	}

	private static int[] sort(int[] all) {
		if (all.length <= 1) {
			return all;
		}
		final int[] left = new int[all.length / 2];
		final int[] right = new int[all.length - left.length];
		System.arraycopy(all, 0, left, 0, left.length);
		System.arraycopy(all, left.length, right, 0, right.length);
		return merge(sort(left), sort(right));
	}

	private static int[] merge(final int[] left, final int[] right) {
		final int[] result = new int[left.length + right.length];
		int leftIndex = 0, rightIndex = 0, resultIndex = 0;
		while (leftIndex < left.length && rightIndex < right.length) {
			if (left[leftIndex] < right[rightIndex]) {
				result[resultIndex] = left[leftIndex];
				leftIndex++;
			} else {
				result[resultIndex] = right[rightIndex];
				rightIndex++;
			}
			resultIndex++;
		}
		int[] rest;
		int restIndex;
		if (leftIndex >= left.length) {
			rest = right;
			restIndex = rightIndex;
		} else {
			rest = left;
			restIndex = leftIndex;
		}
		for (int i = restIndex; i < rest.length; i++) {
			result[resultIndex] = rest[i];
			resultIndex++;
		}
		return result;
	}

	private static void selectSort(int[] list) {
		for (int i = 0; i < list.length - 1; i++) {
			int mIndex = i; // Index of smallest remaining value.
			for (int j = i + 1; j < list.length; j++) {
				if (list[mIndex] > list[j]) {
					mIndex = j; // Remember index of new minimum
				}
			}
			if (mIndex != i) {
				// ... Exchange current element with smallest remaining.
				int temp = list[i];
				list[i] = list[mIndex];
				list[mIndex] = temp;
			}
		}
	}

}