How exactly does compare method in comparator work?

Question

So I want to sort this numbers in list from smallest to biggest. In compare method it look like it is sorting desceding at first, but after the compare method is done with sorting, list is ascended sorted as I was expecting.

Main:

public class Main {
    public static void main(String[] main){
        Integer[] numbers = {3,2,6,1};
        List<Integer> list = Arrays.asList(numbers);

        Collections.sort(list,new SortNumbers());

        System.out.println(list);
    }
}

SortNumbers class:

import java.util.Comparator;

public class SortNumbers implements Comparator<Integer> {
    @Override
    public int compare(Integer i1, Integer i2) {
        if(i1 > i2){
            System.out.println(i1 + " " + i2 + " -> returns 1");
            return 1;
        }else{
            System.out.println(i1 + " " + i2 + " -> returns -1");
            return -1;
        }
    }
}

Output:

2 3 -> returns -1
6 2 -> returns 1
6 3 -> returns 1
1 3 -> returns -1
1 2 -> returns -1
[1, 2, 3, 6]

And also I dont understand why was method comparing 1 and 3 because they are never next to each other.

`if (a > b) return +1, else if (b > a) return -1, else return 0`. Based on this contract comparator sorts comparables — J Asgarov, Feb 16 '22 at 12:09
@ig2jmu the javadoc for compare explains this quite well - https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#compare-T-T- — Jaison, Feb 16 '22 at 12:23
Just to be clear, `Comparator` doesn't *sort* anything. It is `sort(..)` method which handles sorting algorithm (picking *elements* which potentially may need to be rearranged). What `Comparator` does is providing *way* of testing if `elem1>elem2` or `elem1 — Pshemo, Feb 16 '22 at 12:29
Does this answer your question? [How to use Comparator in Java to sort](https://stackoverflow.com/questions/2839137/how-to-use-comparator-in-java-to-sort) — pringi, Feb 16 '22 at 14:46

score 2 · Accepted Answer · answered Feb 16 '22 at 15:28

When you call sort, Java internally uses Tim sort to sort the list. (Note that the actual used sorting method is not a requirement by the language, future updates for Java may chance it even in minor updates)

Since your list is smaller than the typical threshold used for Tim sorts merge vs insertion behavior, it Tim sort delegates sorting your list to insertion sorting.

Java then uses a variant of insertion sort that tries to minimize the comparisons done by using a binary search to find the index.

It starts with:

Sorted: []
Unsorted: [3,2,6,1]

It picks the first number, no further checks are done, sine a list of 1 is always sorted

Sorted: [3]
Unsorted: [2,6,1]

It then looks at the second number, and sees that it is smaller, so it puts it before the 3. One observation here, is that it puts the item under test in the A variable, note that this is an implementation detail. Because the compare function return -1, it knows the item has to be inserted to the left of the checked element)

Comparisons done: (2, 3) => -1
Sorted: [2,3]
Unsorted: [6,1]

Now that we have 2 numbers, we either have to pick the first or second one and hope it was the best choose, java always compares it with the first number

Comparisons done: (6, 2) => 1, (6, 3) => 1
Sorted: [2, 3, 6]
Unsorted: [1]

Now we are the last item, we first call the compare function between 1 and 3. We either get lucky and it returns 0, or we have to do 1 call more to see where the item belongs

Comparisons done: (1, 3) => -1, (1, 2) => -1
Sorted: [1, 2, 3, 6]
Unsorted: []

We are done with the algorithm

How exactly does compare method in comparator work?

1 Answers1