Java: Arrays.sort(Integer) is more faster than Arrays.sort(int) in the worst case:

I suggest O(n) optimization demonstrated below for time-constrained problems:

http://codeforces.me/contest/285/submission/20108766

Edit: my solution above is wrong as outputs mod n may colide (10^6 + 7 is not a prime).

You can add to the blog that one can easily sort primitive datatypes and not get TLE, just by shuffling the array randomly.

I've been a victim so I know :P

My solution got hacked due to this today. Should've used Integer array

public class SortComparison {

static void quickSort(int[] a) {
    long start = System.currentTimeMillis();
    Arrays.sort(a);
    long end = System.currentTimeMillis();
    System.out.println("Arrays.sort() took time : " + (end - start)/1000.0);
}

static void mergeSortWithStreams(int[] a) {
    long start = System.currentTimeMillis();
    List<Integer> listInt = Arrays.stream(a).boxed().sorted().toList();
    long end = System.currentTimeMillis();
    System.out.println("Collections.sort() (mergeSortWithStreams) took time : " + (end - start)/1000.0);
}

static void mergeSortNormal(int[] a) {
    long start = System.currentTimeMillis();
    List<Integer> listInt = new ArrayList<>();
    for(int x : a) {
        listInt.add(x);
    }
    Collections.sort(listInt);
    long end = System.currentTimeMillis();
    System.out.println("Collections.sort() (mergeSortNormal) took time : " + (end - start)/1000.0);
}


public static void main(String[] args) {

    int[] a = new int[10000000];
    for(int i = 0; i < 10000000; i++) {
        a[i] = i;
    }
    int[] b = Arrays.stream(a).toArray();
    int[] c = Arrays.stream(a).toArray();

    //Arrays.sort() is dumb which uses quick sort (which is O(n^2) in worst case scenario)
    quickSort(a);

    //Collections.sort() uses merge sort
    mergeSortWithStreams(b);
    mergeSortNormal(c);
}

} Why I am getting below output now? Shouldn't it be other way round according to your blog. Arrays.sort() took time : 0.011 Collections.sort() (mergeSortWithStreams) took time : 0.248 Collections.sort() (mergeSortNormal) took time : 0.314

`