1-/// Sorts a slice in-place using quicksort with three-way partitioning.
2-/// Handles duplicates efficiently via Dutch National Flag partition,
3-/// uses median-of-three pivot, insertion sort for small partitions,
4-/// and tail-call optimization on the larger partition.
1+/// Sorts a slice in-place using dual-pivot quicksort.
2 pub fn bubble_sort<T: Ord>(slice: &mut [T]) {
6- quicksort(slice);
3+ dual_pivot_quicksort(slice);
4 }
5
6 fn insertion_sort<T: Ord>(slice: &mut [T]) {
13 }
14 }
15
19-fn median_of_three<T: Ord>(slice: &mut [T], a: usize, b: usize, c: usize) -> usize {
20- if slice[a] <= slice[b] {
21- if slice[b] <= slice[c] { b } else if slice[a] <= slice[c] { c } else { a }
22- } else {
23- if slice[a] <= slice[c] { a } else if slice[b] <= slice[c] { c } else { b }
16+fn dual_pivot_quicksort<T: Ord>(slice: &mut [T]) {
17+ let len = slice.len();
18+ if len <= 16 {
19+ insertion_sort(slice);
20+ return;
21 }
25-}
22
27-/// Three-way partition (Dutch National Flag).
28-/// Returns (lt, gt) such that:
29-/// slice[..lt] < pivot
30-/// slice[lt..gt] == pivot
31-/// slice[gt..] > pivot
32-fn partition_three_way<T: Ord>(slice: &mut [T]) -> (usize, usize) {
33- let len = slice.len();
34- let pivot_idx = median_of_three(slice, 0, len / 2, len - 1);
35- slice.swap(pivot_idx, 0);
23+ // Choose pivots at 1/3 and 2/3 positions
24+ let third = len / 3;
25+ let p1_idx = third;
26+ let p2_idx = 2 * third;
27
37- let mut lt = 0;
28+ // Ensure pivot1 <= pivot2
29+ if slice[p1_idx] > slice[p2_idx] {
30+ slice.swap(p1_idx, p2_idx);
31+ }
32+
33+ // Move pivots to ends: pivot1 to position 0, pivot2 to position len-1
34+ slice.swap(0, p1_idx);
35+ slice.swap(len - 1, p2_idx);
36+
37+ // Partition into three regions:
38+ // [0] = pivot1
39+ // [1..lt] < pivot1
40+ // [lt..i] >= pivot1 and <= pivot2
41+ // [gt..len-1] > pivot2
42+ // [len-1] = pivot2
43+ let mut lt = 1;
44+ let mut gt = len - 2;
45 let mut i = 1;
39- let mut gt = len;
46
41- while i < gt {
42- if slice[i] < slice[lt] {
47+ while i <= gt {
48+ if slice[i] < slice[0] {
49 slice.swap(i, lt);
50 lt += 1;
51 i += 1;
46- } else if slice[i] > slice[lt] {
47- gt -= 1;
52+ } else if slice[i] > slice[len - 1] {
53+ while i < gt && slice[gt] > slice[len - 1] {
54+ gt -= 1;
55+ }
56 slice.swap(i, gt);
57+ gt -= 1;
58+ // Re-check slice[i] after swap
59+ if slice[i] < slice[0] {
60+ slice.swap(i, lt);
61+ lt += 1;
62+ }
63+ i += 1;
64 } else {
65 i += 1;
66 }
67 }
53- (lt, gt)
54-}
68
56-fn quicksort<T: Ord>(mut slice: &mut [T]) {
57- loop {
58- let len = slice.len();
59- if len <= 16 {
60- insertion_sort(slice);
61- return;
62- }
69+ // Place pivots in final positions
70+ lt -= 1;
71+ gt += 1;
72+ slice.swap(0, lt);
73+ slice.swap(len - 1, gt);
74
64- let (lt, gt) = partition_three_way(slice);
65-
66- // Recurse on the smaller side, iterate on the larger (tail-call opt)
67- let left_len = lt;
68- let right_len = len - gt;
69- if left_len < right_len {
70- quicksort(&mut slice[..lt]);
71- slice = &mut {slice}[gt..];
72- } else {
73- quicksort(&mut slice[gt..]);
74- slice = &mut {slice}[..lt];
75- }
75+ // Recurse on three partitions
76+ dual_pivot_quicksort(&mut slice[..lt]);
77+ if slice[lt] < slice[gt] {
78+ // Only recurse on middle if pivots are different
79+ dual_pivot_quicksort(&mut slice[lt + 1..gt]);
80 }
81+ dual_pivot_quicksort(&mut slice[gt + 1..]);
82 }
83
84 #[cfg(test)]