How does comparator works internally?

Question

It may sound trivial for you but I am having a hard time visualizing the comparator / array.sort. How can we sort a full array using only 2 arguments? How does it work internally?

for example- Input -[5,3,2,6,8,10,1], Output- [1,2,3,5,6,8,10] Which algo does it use internally? Which 2 objects does it compare at first? (5 compared to 3?) and then what are the next two objects? (5 compared to 2?) or (3 compared to 2)?

public static void main(String[] args) {
         Integer[] tring = new Integer[]{5,3,2,6,8,10,1};
       lol(tring);
       for(int i=0;i<tring.length;i++){
       System.out.println(tring[i]);
       }
    }
    
    public static void lol(Integer[] args) {
      Arrays.sort(args,(h1,h2)->h1-h2);
    }

I might take a step back and look at some simple sorting algorithms (heap, bubble, quick, etc.) You can only compare two values at a time. — Dave Newton, Jun 20 '20 at 21:54
You should look up and study some sort algorithms. Bubble sort is easiest I think and will show you the basics. For primitives, I think Java uses a Quicksort, which will first compare the first element with a pivot. 6 is the most likely pivot value, and the first compare would be with 3 and 8 (not the first element because it gets replaced by the pivot). — markspace, Jun 20 '20 at 21:55
For what a comparator is, see https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html — Enzo Caceres, Jun 20 '20 at 21:56
@Zabuzard I think for primitives it's still using a Quicksort, because primitives don't need a stable sort. For objects it uses Tim sort. — markspace, Jun 20 '20 at 21:56
@markspace You are right. See [this answer](https://stackoverflow.com/a/50854885/2411243). *Java uses Dual-pivot QuickSort to sort array containing primitive data. And it uses Insertion sort if size of array is small (less than 17) and if the size of array is greater than 17 it uses TimSort (Also know as "variation of merge sort") to sort the array containing the object.* — Zabuzard, Jun 20 '20 at 21:58

score 5 · Accepted Answer · 2020-06-21T00:01:53.267

You can visualize the process like this.

Integer[] tring = new Integer[]  {5, 3, 2, 6, 8, 10, 1};
Comparator<Integer> comparator = (a, b) -> {
    System.out.println(Arrays.toString(tring) + " comparing " + a + " and " + b);
    return a.compareTo(b);
};
Arrays.sort(tring, comparator);
System.out.println(Arrays.toString(tring));

result:

[5, 3, 2, 6, 8, 10, 1] comparing 3 and 5
[5, 3, 2, 6, 8, 10, 1] comparing 2 and 3
[5, 3, 2, 6, 8, 10, 1] comparing 6 and 2
[2, 3, 5, 6, 8, 10, 1] comparing 6 and 3
[2, 3, 5, 6, 8, 10, 1] comparing 6 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 8 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 8 and 6
[2, 3, 5, 6, 8, 10, 1] comparing 10 and 5
[2, 3, 5, 6, 8, 10, 1] comparing 10 and 8
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 6
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 3
[2, 3, 5, 6, 8, 10, 1] comparing 1 and 2
[1, 2, 3, 5, 6, 8, 10]

score 2 · Answer 2 · edited Jun 16 '21 at 19:36

The comparator uses a sort called a TimSort

I personally do not feel qualified to explain the timsort algorithm, but I'm sure you can find plenty of explanations on google.

For the second part of your question, the way the comparator uses your two augments is to determine what order any two given values order should be.

So, for example, say if you wanted to sort [6,4] the comparator would use your function a-b and would then plug in the numbers 6 and 4 and get the 2 and because 2 is positive the sort knows that 6 needs to be behind 4. Which would result in [4,6].

How does comparator works internally?

2 Answers2