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.

The first approach that probably comes to mind is to convert it to a list of objects (boxing):

double[] array = new double[1048576];     Arrays.stream(array).boxed().sorted(Collections.reverseOrder())… 

However, boxing each primitive in the array is too slow and causes a lot of GC pressure!

Another approach 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 approach is also slow - particularly if the array is already sorted quite well.

What's a better alternative?

Answer 1

I think it would be best not to re-invent the wheel and use Arrays.sort().

Yes, I saw the "descending" part. The sorting is the hard part, and you want to benefit from the simplicity and speed of Java's library code. Once that's done, you simply reverse the array, which is a relatively cheap O(n) operation. Here's some code I found to do this in as little as 4 lines:

for (int left=0, right=b.length-1; left<right; left++, right--) {     // exchange the first and last     int temp = b[left]; b[left]  = b[right]; b[right] = temp; } 

Answer 2

Java Primitive includes functionality for sorting primitive arrays based on a custom comparator. Using it, and Java 8, your sample could be written as:

double[] array = new double[1048576]; ... Primitive.sort(array, (d1, d2) -> Double.compare(d2, d1), false); 

If you're using Maven, you can include it with:

<dependency>     <groupId>net.mintern</groupId>     <artifactId>primitive</artifactId>     <version>1.2.1</version> </dependency> 

When you pass false as the third argument to sort, it uses an unstable sort, a simple edit of Java's built-in dual-pivot quicksort. This means that the speed should be close to that of built-in sorting.

Full disclosure: I wrote the Java Primitive library.