Pourqu'est-ce que les tris rapides à plusieurs pivots ont été si longtemps marginalisés, alors qu'ils semblaient offrir un potentiel théorique évident pour réduire le nombre de comparaisons ?
Multi-pivot quicksort

Instead of partitioning into two subarrays using a single pivot, multi-pivot quicksort (also multiquicksort) partitions its input into some s number of subarrays using s − 1 pivots. While the dual-pivot case (s = 3) was considered by Sedgewick and others already in the mid-1970s, the resulting algorithms were not faster in practice than the "classical" quicksort. A 1999 assessment of a multiquicksort with a variable number of pivots, tuned to make efficient use of processor caches, found it to increase the instruction count by some 20%, but simulation results suggested that it would be more efficient on very large inputs. A version of dual-pivot quicksort developed by Yaroslavskiy in 2009 turned out to be fast enough to warrant implementation in Java 7, as the standard algorithm to sort arrays of primitives (sorting arrays of objects is done using Timsort). The performance benefit of this algorithm was subsequently found to be mostly related to cache performance, and experimental results indicate that the three-pivot variant may perform even better on modern machines.
Tri rapide à pivots multiples

Au lieu de partitionner en deux sous-tableaux en utilisant un seul pivot, le tri rapide à pivots multiples (également appelé multiquicksort) partitionne son entrée en *s* sous-tableaux en utilisant *s* − 1 pivots. Bien que le cas à deux pivots (*s* = 3) ait été envisagé par Sedgewick et d'autres dès le milieu des années 1970, les algorithmes résultants n'étaient pas plus rapides en pratique que le tri rapide "classique". Une évaluation de 1999 d'un multiquicksort avec un nombre variable de pivots, optimisé pour utiliser efficacement les caches du processeur, a révélé une augmentation du nombre d'instructions d'environ 20 %, mais les résultats de simulation suggéraient qu'il serait plus efficace sur des entrées très volumineuses. Une version du tri rapide à deux pivots développée par Yaroslavskiy en 2009 s'est avérée suffisamment rapide pour justifier son implémentation dans Java 7, en tant qu'algorithme standard pour trier les tableaux de types primitifs (le tri des tableaux d'objets est effectué à l'aide de Timsort). L'avantage de performance de cet algorithme a ensuite été constaté être principalement lié aux performances du cache, et les résultats expérimentaux indiquent que la variante à trois pivots pourrait même mieux performer sur les machines modernes.
### Query ###
Pourqu'est-ce que les tris rapides à plusieurs pivots ont été si longtemps marginalisés, alors qu'ils semblaient offrir un potentiel théorique évident pour réduire le nombre de comparaisons ?

### Main Text ###
Multi-pivot quicksort

Instead of partitioning into two subarrays using a single pivot, multi-pivot quicksort (also multiquicksort) partitions its input into some s number of subarrays using s − 1 pivots. While the dual-pivot case (s = 3) was considered by Sedgewick and others already in the mid-1970s, the resulting algorithms were not faster in practice than the "classical" quicksort. A 1999 assessment of a multiquicksort with a variable number of pivots, tuned to make efficient use of processor caches, found it to increase the instruction count by some 20%, but simulation results suggested that it would be more efficient on very large inputs. A version of dual-pivot quicksort developed by Yaroslavskiy in 2009 turned out to be fast enough to warrant implementation in Java 7, as the standard algorithm to sort arrays of primitives (sorting arrays of objects is done using Timsort). The performance benefit of this algorithm was subsequently found to be mostly related to cache performance, and experimental results indicate that the three-pivot variant may perform even better on modern machines.

### Supplementary Text ###
Tri rapide à pivots multiples

Au lieu de partitionner en deux sous-tableaux en utilisant un seul pivot, le tri rapide à pivots multiples (également appelé multiquicksort) partitionne son entrée en *s* sous-tableaux en utilisant *s* − 1 pivots. Bien que le cas à deux pivots (*s* = 3) ait été envisagé par Sedgewick et d'autres dès le milieu des années 1970, les algorithmes résultants n'étaient pas plus rapides en pratique que le tri rapide "classique". Une évaluation de 1999 d'un multiquicksort avec un nombre variable de pivots, optimisé pour utiliser efficacement les caches du processeur, a révélé une augmentation du nombre d'instructions d'environ 20 %, mais les résultats de simulation suggéraient qu'il serait plus efficace sur des entrées très volumineuses. Une version du tri rapide à deux pivots développée par Yaroslavskiy en 2009 s'est avérée suffisamment rapide pour justifier son implémentation dans Java 7, en tant qu'algorithme standard pour trier les tableaux de types primitifs (le tri des tableaux d'objets est effectué à l'aide de Timsort). L'avantage de performance de cet algorithme a ensuite été constaté être principalement lié aux performances du cache, et les résultats expérimentaux indiquent que la variante à trois pivots pourrait même mieux performer sur les machines modernes.

### Draft ###

### 1. Query Decomposition

"Pourqu'est-ce que les tris rapides à plusieurs pivots ont été si longtemps marginalisés"
→ Why multi-pivot quicksorts marginalized for so long
→ "tris rapides" = quicksort variants, not heap/merge sorts
→ "marginalisés" = ignored/dismissed by practitioners

"alors qu'ils semblaient offrir un potentiel théorique évident"  
→ Theoretical potential obvious for reducing comparisons
→ User assumes theoretical advantage exists
→ Need verify this premise

### 2. Historical Context Mapping

Timeline check:
- Classical quicksort: Hoare 1960s ●
- Multi-pivot variants: Sedgewick mid-1970s ◐
- Cache-aware optimizations: 1990s+ ●
- Modern revival: Java 7, recent papers ●

※ Key gap: practical performance vs theoretical potential

### 3. Theoretical Analysis

Single-pivot quicksort: O(n log n) average, O(n²) worst
Multi-pivot with k pivots: potential improvement?

? Partitioning complexity: k+1 subarrays vs 2 subarrays
? Sorting k elements: O(k log k) vs constant
? Overall: unclear theoretical advantage

⚠ Potential issue: increased overhead from multiple pivots
? Cache locality effects not captured in asymptotic analysis

### 4. Practical Implementation Challenges

Historical factors:
- Code complexity: multi-pivot variants harder to implement
- Memory overhead: storing multiple pivot positions  
- Branch prediction: more complex partitioning logic
- Cache behavior: unclear whether beneficial

⟨H≈0.8⟩ 
Implementation quality cascade... poor early implementations → disappointing benchmarks → marginalization → vicious cycle → theoretical purity vs pragmatic reality gap → modern hardware changes equation → revival...

### 5. Cache-Aware Renaissance

Critical insight: multi-pivot gains emerge from cache optimization, not just theoretical partitioning reduction.

Java 7 dual-pivot quicksort: ●
- 20% improvement claim needs verification
- Cache-friendly partitioning pattern
- Better L1 cache utilization

Three-pivot variants: ○
- Recent experimental results
- Modern CPU architecture benefits
- Still limited adoption

### 6. Synthesis

Multi-pivot quicksorts weren't "marginalized" despite theoretical potential - they were marginalized *because* of practical implementation issues.

Core problem: theoretical asymptotic improvements ≠ practical runtime gains
- Implementation overhead dominated small theoretical advantages
- Cache effects weren't understood until modern architectures
- "Obvious" theoretical potential misleading abstraction

∴ Historical marginalization reflects gap between algorithmic theory and implementation reality, resolved only with cache-aware optimization advances.

Modern revival validates theoretical potential through practical engineering insights.

### Answer###
Les tris rapides à pivots multiples ont effectivement été écartés pendant longtemps malgré leur potentiel théorique, principalement en raison de problèmes de performance pratique et d'optimisation.

Bien que le concept de tri rapide à pivots multiples ait été proposé dès le milieu des années 1970 - notamment par Sedgewick avec la version à deux pivots (dual-pivot) - les algorithmes résultants n'étaient pas plus efficaces en pratique que le tri rapide classique. Cette inefficacité s'explique par le fait que malgré la partition en plusieurs sous-tableaux au lieu de deux, l'augmentation du nombre de pivots entraînait une complexité accrue et des coûts computationnels supérieurs.

Une analyse de 1999 d'un multiquicksort avec un nombre variable de pivots, optimisé pour tirer parti des caches processeur, a révélé une augmentation de 20% du nombre d'instructions. Paradoxalement, les résultats de simulation suggéraient que ce variant pourrait être plus efficace sur des entrées très importantes, mais cette amélioration théorique ne se matérialisait pas dans les applications pratiques.

Le tournant s'est produit avec l'optimisation des performances de cache. La version dual-pivot développée par Yaroslavskiy en 2009 a finalement justifié son adoption dans Java 7, où elle remplace le tri classique pour les tableaux de types primitifs. Cette amélioration s'explique principalement par l'optimisation du comportement du cache plutôt que par une réduction pure du nombre de comparaisons.

Les variantes à trois pivots se montrent même plus prometteuses sur les architectures modernes, confirmant que les gains pratiques des pivots multiples émergent davantage de l'optimisation du cache que de la réduction théorique du nombre d'opérations de comparaison.