What's the sort order of Java's Collections.sort(list, comparator)? small to big or big to small?

Question

Apparently, it's not documented or I missed it.

Here's the link to the documentation and below's the text as an image:

EDIT(17/5): I think too many confused this question to be a comparator question. It is not. The comparator compares between 2 elements. According to that comparison, the list sorted. How? Ascending or Descending?

I'll refine/simplify the question even further: If the comparator decides that element A is smaller than element B. In the sorted list, will element A be located at a lower index than element B?

Solution 1

The sort order is always ascending, where the Comparator defines which items are larger than others.

From the documentation for Collections.sort(List<T> list, Comparator<? super T> c):

Sorts the specified list according to the order induced by the specified comparator.

From the documentation for Comparator.compare(T,T):

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

Solution 2

You (or rather, your comparator) decides.

• If your Comparator's compare(T o1, T o2) return a negative when o1 is less than o2, you get ascending order (demo on ideone).
• If your Comparator's compare(T o1, T o2) return a negative when o1 is greater than o2, you get descending order (demo on ideone).

Another way of saying the same thing would be that sort assumes that the comparator orders the two items passed into it from smaller (o1) to greater (o2), and produces an ascending sort consistent with that ordering.

Solution 3

The documentation of Comparator.compareTo(o1, o2) method says

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

So if you want to sort from natural ordering , that is small to big, then you should write the implementation as defined in the documentation

public int compareTo(Integer o1, Integer o2) {
     int v1 = (o1);
     int v2 = (o2);
     if(v1 == v2) {
        return 0;
     }
     if(v1 < v2) {
        return -1; //return negative integer if first argument is less than second
     }
     return 1;
}

If you want the sorting to be in reverse order, that is big to small

public int compareTo(Integer o1, Integer o2) {
     int v1 = (o1);
     int v2 = (o2);
     if(v1 == v2) {
        return 0;
     }
     if(v1 < v2) {
        return 1;  //do the other way
     }
     return -1;
}

Solution 4

According to the documentation https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#sort(java.util.List,%20java.util.Comparator, the sort implementation for Collections.sort(list, comparator) is mergeSort.

Given the result produced by mergeSort is ascending (https://en.wikipedia.org/wiki/Merge_sort), the sort order of Collections.sort(list, comparator) is ascending.

That is to say if the comparator decides that element A is smaller than element B. In the sorted list, element A will be located at a smaller index than element B.

View more solutions

Comments

[sanbhat]

It depends on how you have written Comparator?

[Rohit Jain]

Have you looked into the API of Comparator? It allows you to define your own sort order.

[AlikElzin-kilaka]

Please look at my edit from 15/7.

[Andy Thomas]

Another way to look at this, more consistent with the Comparator contract, is that the Comparator defines which items are less-than, equal-to, or greater than others.

[nif]

Shouldn't the second sentence be return a positive when o1 is less than o2? Otherwise it would sort the same way as in the first sentence.

[Sergey Kalinichenko]

@nif You're right, I should have "inverted" one part of the condition, not both. Thanks!

[AlikElzin-kilaka]

Why do you think the sorted list is ascending?

[AlikElzin-kilaka]

Why do you think the sorted list is ascending?

[Andy Thomas]

Observation. After calling the method, the list is arranged from the smallest to the largest members, according to the definition provided by the comparator. Before observation, I would have guessed ascending order for parallelism with sibling method Collections.sort(List<T>), which is explicitly documented to be ascending order. The documentation for the method you're using would be improved by explicitly mentioning ascending order, just like its sibling.

[Sergey Kalinichenko]

@kilaka It is always ascending in relation to the comparator: if your comparator is inverted, and it says "less than" when in fact it's greater than, then the output is in descending order.