Может ли операция сортировки не хранить состояние?

Операция сортировки без хранения состояния

Краткий ответ: Да, операция сортировки может не хранить состояние (быть stateless), если используется подходящий алгоритм.

Stateless сортировка

Stateless означает, что алгоритм не хранит дополнительное состояние между операциями, работает с переданными данными и не зависит от предыдущих вызовов.

// ✓ Stateless сортировка: Collections.sort()
public class StatelessSorting {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(5, 2, 8, 1, 9);
        
        // Stateless операция: не использует внешнее состояние
        Collections.sort(numbers);  // O(n log n)
        
        System.out.println(numbers);  // [1, 2, 5, 8, 9]
    }
}

// ✓ Stream API сортировка (также stateless)
public class StreamSorting {
    public static void main(String[] args) {
        List<Integer> numbers = Arrays.asList(5, 2, 8, 1, 9);
        
        // Stateless: создаёт новый отсортированный список
        List<Integer> sorted = numbers.stream()
            .sorted()
            .collect(Collectors.toList());
        
        System.out.println(sorted);  // [1, 2, 5, 8, 9]
    }
}

Как это работает внутри

public class QuickSortExample {
    // Stateless сортировка: не хранит состояние между вызовами
    public static void quickSort(int[] array) {
        if (array == null || array.length == 0) return;
        quickSort(array, 0, array.length - 1);
    }
    
    private static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            quickSort(array, low, pi - 1);    // Рекурсия (стэк, но не состояние)
            quickSort(array, pi + 1, high);
        }
        // Нет глобального состояния!
    }
    
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }
}

Stateless vs Stateful

// ❌ Stateful сортировка (плохо)
public class StatefulSorter {
    private int comparisons = 0;  // СОСТОЯНИЕ!
    private int swaps = 0;        // СОСТОЯНИЕ!
    
    public void sort(int[] array) {
        // Хранит состояние между операциями
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                comparisons++;
                if (array[i] > array[j]) {
                    swap(array, i, j);
                    swaps++;
                }
            }
        }
    }
    
    // Проблема: comparisons и swaps остаются в памяти
    public int getComparisons() {
        return comparisons;  // Зависит от предыдущего состояния
    }
}

// ✓ Stateless сортировка (хорошо)
public class StatelessSorter {
    public void sort(int[] array) {
        // Нет внешнего состояния
        bubbleSort(array);
    }
    
    private void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
    }
    
    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Parallel сортировка (также stateless)

public class ParallelSorting {
    public static void main(String[] args) {
        int[] numbers = new int[]{5, 2, 8, 1, 9, 3, 7, 4, 6};
        
        // Stateless параллельная сортировка
        // Каждый поток работает независимо, нет общего состояния
        Arrays.parallelSort(numbers);
        
        System.out.println(Arrays.toString(numbers));
        // [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

Вывод

Да, сортировка может быть stateless. Большинство встроенных алгоритмов сортировки в Java (QuickSort, MergeSort, TimSort) не хранят состояние между вызовами.