java - How to sort int array efficiently -

i have array of ints

int array[] = ... 

and can sort using

arrays.sort(array); 

but arrays.sort uses quicksort, result in o(n^2) complexity. had idea convert list , sort (mergesort used, upper bound o(n log n)), drawback creates lot of objects due boxing int integer.

my third approach :

array = arrays.stream(array).sorted().toarray(); 

i operate on intstream, unfortunately complexity isn't mentioned in documentation.

i looking similar questions , have found big-o complexity of java.util.stream.stream<t>.sorted() isn't helpful @ all, because there 2 different answers (first of course partially wrong, because arrays.sort isn't o(n log n)). second 1 ? haven't found proof.

you should investigate heapsort, while slower guarantees o(n log n). quicksort vs heapsort

there textbook explanation here.