CareerCup

Since it is mentioned that the sorting does not need to be in place, use of bucket sort would do the sorting in O(n).
Since, it is given that every element can only range from 1 to 10, we can have an HashMap having each 1 to 10 as keys and their corresponding counts as values. After one iteration over the array, we get all the counts in the HashMap, which we could then use to updated the array with sorted elements.

public static void sortIntegers(int[] n){
		int[] count = new int[10];
		for(int value : n)
			count[value-1]++;
		for(int index = 0; index < 10; index++)
			for(int j = 0; j < count[index]; j++)
			System.out.print(index+1+" ");
		
	}

public static void sortIntegers(int[] n){
		int[] count = new int[10];
		for(int value : n)
			count[value-1]++;
		for(int index = 0; index < 10; index++)
			for(int j = 0; j < count[index]; j++)
			System.out.print(index+1+" ");

}

package com.home.careercup;

import java.util.Arrays;

public class CountingSortFor1MIntegers {

    /**
     * You are given an integer array n. Complete the function
     * sortIntegers which takes as an argument, an integer array
     * n of up to 1 million integers such that 1 <= n_i <= 10.
     * for every element n_i in the array, and returns the sorted
     * array. The sort does not need to occur in-place.
     * Please do not call a standard sorting function like
     * quicksort, you can do better. A sample input is
     * {3, 1, 4, 1, 5, 9, 2, 6, 5} and the corresponding output is
     * {1, 1, 2, 3, 4, 5, 5, 6, 9}.
     * Constraints: i <= 10^9; 1 <= n_i <= 10
     *
     * @param args
     */
    public static void main(String[] args) {
        int [] sample = new int [] {3, 1, 4, 1, 5, 9, 2, 6, 5};
        sort (sample);
        System.out.println(Arrays.toString(sample));

    }

    /*
    counting sort (in place)
     */
    static void sort(int[] arr) {
        int f[] = new int[11];

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <=0 || arr [i]>10)
            throw new RuntimeException(String.format("array value out of range, index=%d, value=%d", i, arr [i]));
            f[arr[i]]++;
        }

        for (int i = 1,j=0; i <f.length ; j+= f[i],i++) {
            if (f[i] >0 )
                Arrays.fill(arr,j, j+ f[i],i);
        }
    }
}