Да, существуют алгоритмы сортировки, которые не используют дополнительную память для хранения промежуточных данных — их называют in-place алгоритмами.

Примеры таких алгоритмов:

Сортировка пузырьком (Bubble Sort)
Сортировка вставками (Insertion Sort)
Сортировка выбором (Selection Sort)
Быстрая сортировка (Quick Sort) — при аккуратной реализации
Сортировка кучей (Heap Sort)

Эти алгоритмы меняют порядок элементов непосредственно в исходном массиве, не выделяя дополнительной памяти под копии или вспомогательные структуры.

Пример быстрой сортировки in-place на Java:

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

private int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Таким образом, in-place сортировки позволяют экономить память, но иногда могут уступать по скорости или стабильности сортировкам, которые используют дополнительную память.

Возможно ли реализовать алгоритм сортировки, который не использует дополнительную память для сохранения промежуточных данных?