Est-il possible de réaliser un algorithme de tri qui n'utilise pas de mémoire supplémentaire pour stocker des données intermédiaires?

Oui, il existe des algorithmes de tri qui n’utilisent pas de mémoire supplémentaire pour stocker des données intermédiaires — ils sont appelés algorithmes in-place.

Exemples de tels algorithmes :

• Tri à bulles (Bubble Sort)
• Tri par insertion (Insertion Sort)
• Tri par sélection (Selection Sort)
• Tri rapide (Quick Sort) — avec une implémentation soignée
• Tri par tas (Heap Sort)

Ces algorithmes modifient directement l’ordre des éléments dans le tableau d’origine, sans allouer de mémoire supplémentaire pour des copies ou des structures auxiliaires.

Exemple de tri rapide in-place en 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;
}

Ainsi, les tris in-place permettent d’économiser de la mémoire, mais peuvent parfois être moins rapides ou moins stables que ceux qui utilisent de la mémoire supplémentaire.