performance of int Array vs Integer Array

Question

Today when I submitted a solution to codeforces, I used int[] array and my submission got TLE(Time limit exceeded) & after changing it to Integer[] array surprisingly it got AC. I didn't get how the 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 it is quite simple: the time complexity of the solution with Integer is better.

Sounds strange, doesn't it?

Arrays.sort uses a dual pivot quick sort for primitives, which works in O(N^2) time in the worst case. The test case your solution fails is a specially constructed anti-quick sort test.

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

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

P.S. Things like this happen more or less frequently in competitive programming, so I'll recommend to either sort arrays of objects or to use collections.