Identify the algorithm by counting

import java.util.*;
import java.util.function.*;

/**
 * Warm-up: make Arrays.sort tell you which algorithm it ran.
 *
 * It never reports that. But the comparator is a function you supply, so you
 * can count how often it is called — and the count is a fingerprint.
 */
public class Starter {

    record Emp(String name, String dept) {}

    static List<Emp> staff() {
        return List.of(
            new Emp("Ana",  "Eng"),   new Emp("Bo",  "Sales"),
            new Emp("Cara", "Eng"),   new Emp("Dev", "Sales"),
            new Emp("Eli",  "Eng"),   new Emp("Fay", "Ops"));
    }

    public static void main(String[] args) {

        // TODO 1: write a comparator wrapper that counts every call:
        //
        //   static <T> Comparator<T> counting(Comparator<T> inner, int[] calls)
        //
        // It delegates to `inner` and increments calls[0] each time.

        // TODO 2: build an Integer[] of 1,000,000 already-sorted values, sort
        // it with your counting comparator, and print the count. Predict the
        // number BEFORE you run it. Most people predict n log n.

        // TODO 3: repeat for reverse-sorted input. The count is the same.
        // Work out what the algorithm must be doing to achieve that, given it
        // has to physically reverse a million elements.

        // TODO 4: repeat for random input. Compare it against n * log2(n),
        // which you can compute as n * (Math.log(n) / Math.log(2)).

        // TODO 5: now build "sorted except the last 1000, which are random".
        // This is what real data usually looks like. Is the count closer to
        // the sorted case or the random one? Say why that matters at work.

        // TODO 6: stability. Sort staff() by name, then by dept, and print
        // dept/name for each. Then do the same but use a sort you write
        // yourself — any correct quicksort — for the dept pass. Both results
        // are correctly sorted by dept. Describe the difference in one
        // sentence, and say which one the JDK gives you.

        // TODO 7: primitives. Build an int[] of 2,000,000 ascending values and
        // another of random ones, sort each with Arrays.sort(int[]) and time
        // them (warm up first by sorting throwaway clones a few times).
        // The textbook answer says this path is a quicksort. Does the timing
        // agree? What does the difference rule out?

        // TODO 8: try to detect instability in Arrays.sort(int[]). Write the
        // test. When you cannot, say precisely why — that sentence is the
        // answer to "why does it depend on the type?".
    }
}