How does Collections.sort() work internally?

Collections.sort() is used to arrange elements in a list in ascending order based on their natural ordering or a custom Comparator. Internally, Java uses TimSort, a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. TimSort is highly optimized for real-world data and performs exceptionally well on partially sorted collections.

Key Points: • Collections.sort() uses TimSort, which is stable and preserves the relative order of equal elements. • For custom objects, sorting is based on the compareTo() method of Comparable or a supplied Comparator. • The average and worst-case time complexity is O(n log n), making it efficient for large datasets.

Example: Suppose an employee list is already partially sorted by employee ID. TimSort detects these sorted portions (runs) and takes advantage of them, reducing the number of comparisons and improving performance compared to traditional sorting algorithms.

Code Example:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortExample {

    public static void main(String[] args) {

        List<Integer> numbers =
                Arrays.asList(50, 10, 40, 20, 30);

        Collections.sort(numbers);

        System.out.println(numbers);
    }
}

Interview Tip: A concise interview answer is: Collections.sort() internally uses TimSort, a hybrid of Merge Sort and Insertion Sort. It is a stable sorting algorithm with O(n log n) complexity, optimized for partially sorted data, and can sort elements using either natural ordering or a custom Comparator.