Sorting a 2-dimensional array with counting sort

Question

The task I'm solving is:

1. Sort a list by its keys
2. Print out the corresponding values on one line separated by whitespace
3. Replace the values of the first half of the input to "-"
4. Use Counting Sort

The following code works, but times out when given 1 million entries:

public class Solution { static String[] countingSort(String[][] arr) { String[] result = new String[arr.length]; int[] count = new int[100]; for(int i=0;i<arr.length;i++) { count[Integer.parseInt(arr[i][0])]++; } for(int i=1;i<count.length;i++) { count[i] += count[i-1]; } for(int i=arr.length-1;i>=0;i--) { result[count[Integer.parseInt(arr[i][0])]-1] = arr[i][1]; count[Integer.parseInt(arr[i][0])]--; } return result; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); String[][] arr = new String[n][2]; for(int a0 = 0; a0 < n; a0++){ int a = in.nextInt(); arr[a0][0] = Integer.toString(a); if(a0<n/2) { String s =in.next(); arr[a0][1] = "-"; } else { String s = in.next(); arr[a0][1] = s; } } in.close(); String[] result = countingSort(arr); for(int i=0;i<result.length;i++) { System.out.print(result[i]+" "); } } 

1. input is being put into 2 dimensional array. values are being replaced with "-" for first half of the values. [array: arr]
2. Array is passed to method [array: arr, method: countingSort]
3. New array of size 100 is being created as the keys are 0 < key < 100 [array: count]
4. occurrences of each key are added in the newly created array [array: count]
5. values of the array are being accumulated [array: count]
6. the values of the corresponding key are being sorted into the result array according to the count array.
7. result is being returned.

Particular concerns:

1. How can the code be improved in order to increase performance and avoid timeout using counting sort?
2. Are there any other possibilities (sorting algorithms) which have higher performance (can solve the problem faster)?

Answer 1

Algorithm is ok, and there is nothing faster than counting sort. You just need to use single System.out.print:

StringBuilder sb = new StringBuilder(); for (int i = 0; i < result.length; i++) { sb.append(result[i]).append(" "); } System.out.print(sb.toString()); 

It is faster than many separate calls;