Hi,

I implemented a solution to 439B where the most time consuming step was using Arrays.sort. On test case 29 it times out at 1000 ms if I sort using an int[]. However, I pass, and use at most 280 ms on test case 29 if I sort using an Integer[]. Can someone explain why java.util.Arrays.sort(), on Codeforces, is more than 3x faster when using Integer[] rather than int[] in this case? The size of the array is 100,000 and the integers inside the array are from 1 to 100,000.

Thanks

My code is here:

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();    // number of subjects
    long x = sc.nextLong();    // initial per-chapter learning power of a subject
    
    Integer[] cps = new Integer[n];  // number of chapters per subject
    for (int i = 0; i < n; ++i) {
      cps[i] = sc.nextInt();
    }

    Arrays.sort(cps);  // Times out when cps is an int[].  Must be Integer[].
    
    long totalTime = 0;
    for (int i = 0; i < n; ++i) {
      totalTime += cps[i] * x;
      if (x != 1) {
        --x;
      }
    }
    
    System.out.println(totalTime);
  }
}