How to sort int array efficiently

Question

I have array of ints

int array[] = ...

and I can sort it using

Arrays.sort(array);

but Arrays.sort uses quicksort, which sometimes result in O(n^2) complexity. I had an idea to convert it to List and then sort it (mergesort is used, so upper bound is O(n log n)), but the drawback is that it creates a lot of objects due to boxing from int to Integer.

My third approach is this :

array = Arrays.stream(array).sorted().toArray();

I operate only on IntStream, but unfortunately the complexity isn't mentioned in the documentation.

I was looking for similar questions and I have found only this Big-O complexity of java.util.stream.Stream<T>.sorted() which isn't helpful at all, because there are two different answers (first is of course partially wrong, because Arrays.sort isn't always O(n log n)). What about the second one ? I haven't found the proof.

Answer 1

You should investigate Heapsort, while slightly slower it guarantees O(n Log n). Quicksort vs heapsort

There is also the textbook explanation here.

Answer 2

If the range of integers is small you can use Counting Sort, which uses numbers as array-indexes and, unlike comparison-sort algorithms that have a lower bound of O(nlogn) (eg Quicksort or Mergesort), it has a complexity of O(n+k), where k is the range between your min and max value.

Which algorithm to choose always depends on any extra knowledge you may have regarding the distribution of the array elements.

Answer 3

O(n) time, O(1) space

Use IntArrays.unstableSort(int[] a) from fastutil library.

It uses in-place radix sort for big enough arrays and quicksort for small arrays:

if (to - from >= RADIX_SORT_MIN_THRESHOLD) {
  radixSort(a, from, to);
} else {
  quickSort(a, from, to);
}

O(n log(n)) time, O(n) space and Java 14+

Arrays.sort uses quicksort, which sometimes result in O(n^2) complexity

This is only true if you are using Java 13 or earlier versions. Starting from Java 14 Arrays.sort(int[]) guarantees O(n log(n)) performance in the worst case:

This algorithm offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations.

https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Arrays.html#sort(int%5B%5D)

This is achieved by resorting to heapsort if recursion becomes too deep:

if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
  heapSort(a, low, high);
  return;
}

Answer 4

Just implement the mergesort yourself, it's no rocket science. After you have implemented it, do take a little time to run some benchmarks and compare the performance of you implementation with that of Arrays.sort. There may be some surprises waiting for you there.

Also, read up on premature optimization, I think you might find the notion useful.