Sort arrays of primitive types in descending order

Question

I've got a large array of primitive types (double). How do I sort the elements in descending order?

Unfortunately the Java API doesn't support sorting of primitive types with a Comparator.

One workaround would be to sort and then reverse:

double[] array = new double[1048576];
...
Arrays.sort(array);
// reverse the array
for (int i = 0; i < array.length / 2; i++) {
     // swap the elements
     double temp = array[i];
     array[i] = array[array.length - (i + 1)];
     array[array.length - (i + 1)] = temp;
}

This is slow - particularly if the array is already sorted quite well.

What's a better alternative?

Answer 1

Your implementation (the one in the question) is faster than e.g. wrapping with toList() and using a comparator-based method. Auto-boxing and running through comparator methods or wrapped Collections objects is far slower than just reversing.

Of course you could write your own sort. That might not be the answer you're looking for, but note that if your comment about "if the array is already sorted quite well" happens frequently, you might do well to choose a sorting algorithm that handles that case well (e.g. insertion) rather than use Arrays.sort() (which is mergesort, or insertion if the number of elements is small).

Answer 2

If performance is important, and the list usually already is sorted quite well.

Bubble sort should be one of the slowest ways of sorting, but I have seen cases where the best performance was a simple bi-directional bubble sort.

So this may be one of the few cases where you can benefit from coding it yourself. But you really need to do it right (make sure at least somebody else confirms your code, make a proof that it works etc.)

As somebody else pointed out, it may be even better to start with a sorted array, and keep it sorted while you change the contents. That may perform even better.