Какой тип сортировки используется при передаче в Collections.sort?

Алгоритм сортировки в Collections.sort()

Основной алгоритм

Collections.sort() в Java использует Timsort (версия для объектов) и Dual-Pivot Quicksort (в зависимости от версии JDK).

В современных версиях Java (8+):

• Timsort для объектов в Collections.sort()
• Dual-Pivot Quicksort для примитивов в Arrays.sort()

Что такое Timsort?

Timsort — это гибридный алгоритм, созданный Тимом Петерсом для Python, адаптирован в Java:

• Комбинирует Merge Sort и Insertion Sort
• O(n log n) в худшем случае (гарантировано)
• O(n) в лучшем случае (уже отсортированные данные)
• Стабильная сортировка — сохраняет порядок равных элементов

Как работает Timsort?

Шаг 1: Разделение на части (runs)

Massив разбивается на малые отсортированные части (обычно 32-64 элемента):

Исходный массив: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

Разбиение на runs:
Run 1: [1, 3, 4, 5]
Run 2: [2, 5, 6, 9]
Run 3: [3]

Шаг 2: Сортировка внутри каждой части

Каждый run сортируется Insertion Sort (быстро для малых массивов):

// Insertion Sort для маленького run
for (int i = 1; i < run.size(); i++) {
    int key = run[i];
    int j = i - 1;
    while (j >= 0 && run[j] > key) {
        run[j + 1] = run[j];
        j--;
    }
    run[j + 1] = key;
}

Шаг 3: Слияние (Merge)

Отсортированные runs сливаются попарно с использованием Merge Sort:

Шаг 1:
[1, 3, 4, 5] + [2, 5, 6, 9] = [1, 2, 3, 4, 5, 5, 6, 9]
[3] = [3]

Шаг 2:
[1, 2, 3, 4, 5, 5, 6, 9] + [3] = [1, 2, 3, 3, 4, 5, 5, 6, 9]

Пример: Collections.sort() на практике

import java.util.*;

public class SortExample {
    public static void main(String[] args) {
        // Список объектов
        List<Integer> numbers = Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5, 3);
        
        // Collections.sort использует Timsort
        Collections.sort(numbers);
        
        System.out.println(numbers);  // [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]
    }
}

Сортировка с Comparator

List<String> words = Arrays.asList("zebra", "apple", "banana", "cherry");

// По алфавиту
Collections.sort(words);
System.out.println(words);  // [apple, banana, cherry, zebra]

// По длине
Collections.sort(words, Comparator.comparingInt(String::length));
System.out.println(words);  // [apple, zebra, banana, cherry]

// В обратном порядке
Collections.sort(words, Collections.reverseOrder());
System.out.println(words);  // [zebra, cherry, banana, apple]

Сортировка объектов

class Person {
    String name;
    int age;
    
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class ObjectSortExample {
    public static void main(String[] args) {
        List<Person> people = Arrays.asList(
            new Person("Alice", 30),
            new Person("Bob", 25),
            new Person("Charlie", 35)
        );
        
        // По возрасту
        Collections.sort(people, Comparator.comparingInt(p -> p.age));
        people.forEach(System.out::println);
        // Bob (25)
        // Alice (30)
        // Charlie (35)
        
        // По имени
        Collections.sort(people, Comparator.comparing(p -> p.name));
        people.forEach(System.out::println);
        // Alice (30)
        // Bob (25)
        // Charlie (35)
    }
}

Временная сложность Timsort

Стабильность сортировки

Timsort стабилен — элементы с одинаковым значением сохраняют исходный порядок:

class Student {
    String name;
    int grade;
    
    Student(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }
    
    @Override
    public String toString() {
        return name + ":" + grade;
    }
}

public class StableSort {
    public static void main(String[] args) {
        List<Student> students = Arrays.asList(
            new Student("Alice", 85),
            new Student("Bob", 85),
            new Student("Charlie", 90)
        );
        
        Collections.sort(students, Comparator.comparingInt(s -> s.grade));
        
        students.forEach(System.out::println);
        // Alice:85 (сохранён порядок)
        // Bob:85
        // Charlie:90
    }
}

Сравнение с другими сортировками

Оптимизация: когда использовать Collections.sort()

// ✅ Используй Collections.sort для списков
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5));
Collections.sort(list);

// ✅ Или Stream API
List<Integer> sorted = list.stream()
    .sorted()
    .collect(Collectors.toList());

// ❌ Не используй Collections.sort для массивов
int[] arr = {3, 1, 4};
Collections.sort(...);  // Ошибка!

// ✅ Используй Arrays.sort для массивов
Arrays.sort(arr);  // Использует Dual-Pivot Quicksort

Внутренняя реализация Timsort (упрощённо)

public class TimsortSimplified {
    static final int MIN_RUN = 32;
    
    public static void timsort(List<Integer> list) {
        int n = list.size();
        
        // Шаг 1: Разбиение на runs и сортировка каждого
        for (int start = 0; start < n; start += MIN_RUN) {
            int end = Math.min(start + MIN_RUN, n);
            insertionSort(list, start, end);
        }
        
        // Шаг 2: Слияние runs
        for (int size = MIN_RUN; size < n; size *= 2) {
            for (int start = 0; start < n; start += size * 2) {
                int mid = start + size;
                int end = Math.min(start + size * 2, n);
                if (mid < end) {
                    merge(list, start, mid, end);
                }
            }
        }
    }
    
    private static void insertionSort(List<Integer> list, int start, int end) {
        for (int i = start + 1; i < end; i++) {
            int key = list.get(i);
            int j = i - 1;
            while (j >= start && list.get(j) > key) {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, key);
        }
    }
    
    private static void merge(List<Integer> list, int start, int mid, int end) {
        // Реализация слияния двух отсортированных подмассивов
    }
}

Практический пример: сортировка по нескольким критериям

class Employee {
    String name;
    String department;
    int salary;
    
    Employee(String name, String department, int salary) {
        this.name = name;
        this.department = department;
        this.salary = salary;
    }
    
    @Override
    public String toString() {
        return name + " (" + department + ", " + salary + ")";
    }
}

public class ComplexSort {
    public static void main(String[] args) {
        List<Employee> employees = Arrays.asList(
            new Employee("Alice", "IT", 5000),
            new Employee("Bob", "HR", 4000),
            new Employee("Charlie", "IT", 6000),
            new Employee("David", "HR", 4500)
        );
        
        // Сортировка по отделу, затем по зарплате
        Collections.sort(employees, 
            Comparator.comparing((Employee e) -> e.department)
                      .thenComparingInt(e -> e.salary)
        );
        
        employees.forEach(System.out::println);
        // Bob (HR, 4000)
        // David (HR, 4500)
        // Alice (IT, 5000)
        // Charlie (IT, 6000)
    }
}

Резюме

Collections.sort() использует Timsort, который:

• Гарантирует O(n log n) в любом случае
• Работает очень быстро на уже частично отсортированных данных (O(n))
• Является стабильным (сохраняет порядок равных элементов)
• Рекомендуется для большинства случаев сортировки в Java
• Комбинирует преимущества нескольких алгоритмов для оптимальной производительности