Sort large arrays of primitive types in descending order

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;
}

Heres a one-liner, using streams in Java 8

int arr = new int[]{1,2,3,4,5};
Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();

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).

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).

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.

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.

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

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;
}

Understand it's a very old post but I stumbled upon a similar problem trying to sort primitive int arrays, so posting my solution. Suggestions/comments welcome -

int[] arr = {3,2,1,3};
List<Integer> list = new ArrayList<>();
Arrays.stream(arr).forEach(i -> list.add(i));
list.stream().sorted(Comparator.reverseOrder()).forEach(System.out::println);

double s =-1;
   double[] n = {111.5, 111.2, 110.5, 101.3, 101.9, 102.1, 115.2, 112.1};
   for(int i = n.length-1;i>=0;--i){
      int k = i-1;
      while(k >= 0){
          if(n[i]>n[k]){
              s = n[k];
              n[k] = n[i];
              n[i] = s;
          }
          k --;
      }
   }
   System.out.println(Arrays.toString(n));
 it gives time complexity O(n^2) but i hope its work

Here's a full program that sorts objects based on a inner field.

package Algorithms.BranchAndBound;

import java.util.Arrays;
import java.util.Comparator;

public class KnapSack01 {
    private class ItemVals {
        double weight;
        double cost;
        double ratio;

        public ItemVals(double weight, double cost) {
            this.weight = weight;
            this.cost = cost;
            this.ratio = weight/cost;
        }
    }

    public ItemVals[] createSortedItemVals(double[] weight, double[] cost) {
        ItemVals[] itemVals = new ItemVals[weight.length];
        for(int i = 0; i < weight.length; i++) {
            ItemVals itemval = new ItemVals(weight[i], cost[i]);
            itemVals[i] = itemval;
        }
        Arrays.sort(itemVals, new Comparator<ItemVals>() {
            @Override
            public int compare(ItemVals o1, ItemVals o2) {
                return Double.compare(o2.ratio, o1.ratio);
            }
        });
        return itemVals;
    }

    public void printItemVals(ItemVals[] itemVals) {
        for (int i = 0; i < itemVals.length; i++) {
            System.out.println(itemVals[i].ratio);
        }
    }

    public static void main(String[] args) {
        KnapSack01 knapSack01 = new KnapSack01();
        double[] weight = {2, 3.14, 1.98, 5, 3};
        double[] cost = {40, 50, 100, 95, 30};
        ItemVals[] itemVals = knapSack01.createSortedItemVals(weight, cost);
        knapSack01.printItemVals(itemVals);
    }
}

Below is my solution, you can adapt it to your needs.

How does it work? It takes an array of integers as arguments. After that it will create a new array which will contain the same values as the array from the arguments. The reason of doing this is to leave the original array intact.

Once the new array contains the copied data, we sort it by swapping the values until the condition if(newArr[i] < newArr[i+1]) evaluates to false. That means the array is sorted in descending order.

For a thorough explanation check my blog post here.

public static int[] sortDescending(int[] array)
{
    int[] newArr = new int[array.length];

    for(int i = 0; i < array.length; i++)
    {
        newArr[i] = array[i];
    }

    boolean flag = true;
    int tempValue;

    while(flag) 
    {
        flag = false;

        for(int i = 0; i < newArr.length - 1; i++) 
        {
            if(newArr[i] < newArr[i+1])
            {
                tempValue = newArr[i];
                newArr[i] = newArr[i+1];
                newArr[i+1] = tempValue;
                flag = true;
            }
        }
    }

    return newArr;
}

double[] array = new double[1048576];

...

By default order is ascending

To reverse the order

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