Is het mogelijk om een sorteeralgoritme te implementeren dat geen extra geheugen gebruikt voor het opslaan van tussentijdse gegevens?

Ja, er bestaan sorteeralgoritmen die geen extra geheugen gebruiken om tussentijdse gegevens op te slaan — ze worden in-place algoritmen genoemd.

Voorbeelden van dergelijke algoritmen:

• Bubble Sort (Bubbelsortering)
• Insertion Sort (Invoegsortering)
• Selection Sort (Selectiesortering)
• Quick Sort (Snelle sortering) — bij zorgvuldige implementatie
• Heap Sort (Hefsortering)

Deze algoritmen wijzigen de volgorde van de elementen direct in de oorspronkelijke array, zonder extra geheugen toe te wijzen voor kopieën of hulppstructuren.

Voorbeeld van in-place quick sort in 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;
}

Op deze manier besparen in-place sorteringen geheugen, maar kunnen ze soms trager of minder stabiel zijn dan sorteringen die extra geheugen gebruiken.