A1

public static int[] countingSort(int[] a) {

		if (a.length == 0) {

			return a;
		}

		int max = a[0];

		for (int i = 1; i < a.length; i++)

			if (a[i] > max)

				max = a[i];

		int[] sorted = new int[a.length];

		int[] count = new int[max > a.length ? max + 1: a.length + 1];

		for (int element = 0; element < a.length; element++)

			count[a[element]]++;

		for (int i = 0, j = 0; i < count.length; i++) {

			while (count[i] != 0) {

				sorted[j] = i;

				count[i]--;

				j++;
			}
		}

		return sorted;	// return an array with sorted values
	}

	/*
	 * This method makes a list of integers between 0-524287
	 * The sorting method used is Radix Sort
	 */
	public static int[] radixSort(int[] a) {

		if (a.length == 0) {

			return a;
		}

		int max = a[0];

		for (int i = 1; i < a.length; i++) {

			if (a[i] > max) {

				max = a[i];
			}
		}

		int num = 1;

		int[] arr2 = new int[1000];

		while (max / num > 0) {

			int[] arr = new int[10];

			for (int i = 0; i < a.length; i++)

				arr[((a[i] / num) % 10)]++;

			for (int i = 1; i < arr.length; i++)

				arr[i] += arr[i - 1];

			for (int i = a.length - 1; i >= 0; i--)

				arr2[--arr[(a[i] / num) % 10]] = a[i];

			for (int i = 0; i < a.length; i++)

				a[i] = arr2[i];

			num *= 10;

		}

		return a;	// return an array with sorted values
	}