Este posibil să implementăm un algoritm de sortare care să nu utilizeze memorie suplimentară pentru stocarea datelor intermediare?

Da, există algoritmi de sortare care nu utilizează memorie suplimentară pentru stocarea datelor intermediare — aceștia sunt numiți algoritmi in-place.

Exemple de astfel de algoritmi:

• Sortarea cu bule (Bubble Sort)
• Sortarea prin inserție (Insertion Sort)
• Sortarea prin selecție (Selection Sort)
• Sortarea rapidă (Quick Sort) — cu o implementare atentă
• Sortarea prin heap (Heap Sort)

Acești algoritmi schimbă ordinea elementelor direct în array-ul original, fără a aloca memorie suplimentară pentru copii sau structuri auxiliare.

Exemplu de sortare rapidă in-place în 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;
}

Astfel, sortările in-place permit economisirea memoriei, dar uneori pot fi mai lente sau mai puțin stabile decât cele care utilizează memorie suplimentară.