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

There's been some confusion about Arrays.asList in the other answers. If you say

double[] arr = new double[]{6.0, 5.0, 11.0, 7.0};
List xs = Arrays.asList(arr);
System.out.println(xs.size());  // prints 1

then you'll have a List with 1 element. The resulting List has the double[] array as its own element. What you want is to have a List<Double> whose elements are the elements of the double[].

Unfortunately, no solution involving Comparators will work for a primitive array. Arrays.sort only accepts a Comparator when being passed an Object[]. And for the reasons describe above, Arrays.asList won't let you make a List out of the elements of your array.

So despite my earlier answer which the comments below reference, there's no better way than manually reversing the array after sorting. Any other approach (such as copying the elements into a Double[] and reverse-sorting and copying them back) would be more code and slower.

Answer 3

I am not aware of any primitive sorting facilities within the Java core API.

From my experimentations with the D programming language (a sort of C on steroids), I've found that the merge sort algorithm is arguably the fastest general-purpose sorting algorithm around (it's what the D language itself uses to implement its sort function).

• One implementation in Java
• Another implementation
• One more implementation

Answer 4

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.

Answer 5

You cannot use Comparators for sorting primitive arrays.

Your best bet is to implement (or borrow an implementation) of a sorting algorithm that is appropriate for your use case to sort the array (in reverse order in your case).

Answer 6

Your algorithm is correct. But we can do optimization as follows: While reversing, You may try keeping another variable to reduce backward counter since computing of array.length-(i+1) may take time! And also move declaration of temp outside so that everytime it needs not to be allocated

double temp;

for(int i=0,j=array.length-1; i < (array.length/2); i++, j--) {

 // swap the elements
 temp = array[i];
 array[i] = array[j];
 array[j] = temp;

}

Answer 7

double[] array = new double[1048576]; ...

By deafualt Order is Ascending

To reverse the order

Arrays.sort(array,Collections.reverseOrder());

Answer 8

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.