Performance array int Array vs Integer

Question

Today, when I presented the solution for Codeforces, I used the int [] array, and my view got TLE (time limit exceeded) and after changing it to the Integer [] array, it unexpectedly got AC. I did not understand how performance is improved.

import java.io.*; import java.lang.reflect.Array; import java.util.*; public class Main { static class Task { public void solve(InputReader in, PrintWriter out) throws Exception { int n = in.nextInt(); Integer[] a = new Integer[n]; for (int i = 0; i < n; i++) a[i] = in.nextInt(); Arrays.sort(a); long count = 0; for (int i = 0; i < n; i++) count += Math.abs(i + 1 - a[i]); out.println(count); } } public static void main(String[] args) throws Exception{ InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); Task task = new Task(); task.solve(in, out); out.close(); } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } } 

Answer 1

The reason for this is quite simple: the complexity of the solution time with Integer better.

Sounds weird, right?

Arrays.sort uses double sliding sorting for primitives, which works O(N^2) times in the worst case. In the test case, your solution fails - it is a specially developed anti-slip sorting method.

However, the version for objects uses merge sorting, which works in O(N * log N) for any possible input.

Note that it is not part of the Java language specification (it does not say how the sort method should be implemented), but it works like in most real implementations (for example, this is the case for openjdk-8 )

PS Such things happen more or less often in competitive programming, so I recommend either sorting arrays of objects, or using collections.