feat(collection): Replace quickSort with pdqsort for performance and robustness (#922)
Co-authored-by: Nate Bosch <nbosch1@gmail.com>
diff --git a/pkgs/collection/CHANGELOG.md b/pkgs/collection/CHANGELOG.md
index 6517421..5773f47 100644
--- a/pkgs/collection/CHANGELOG.md
+++ b/pkgs/collection/CHANGELOG.md
@@ -11,6 +11,8 @@
- Add `PriorityQueue.of` constructor and optimize adding many elements.
- Address diagnostics from `strict_top_level_inference`.
- Run `dart format` with the new style.
+- Replace `quickSort` implementation with a more performant and robust
+ Pattern-defeating Quicksort (pdqsort) algorithm.
## 1.19.1
diff --git a/pkgs/collection/benchmark/benchmark_utils.dart b/pkgs/collection/benchmark/benchmark_utils.dart
new file mode 100644
index 0000000..d819868
--- /dev/null
+++ b/pkgs/collection/benchmark/benchmark_utils.dart
@@ -0,0 +1,235 @@
+// Copyright (c) 2025, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/// Reusable utilities for benchmarking sorting algorithms.
+library;
+
+import 'dart:math';
+import 'package:benchmark_harness/benchmark_harness.dart';
+
+// Sink variable to prevent the compiler from optimizing away benchmark code.
+int sink = 0;
+
+/// The aggregated result of a benchmark run.
+class BenchmarkResult {
+ final double mean;
+ final int median;
+ final double stdDev;
+ final List<int> allTimes;
+
+ BenchmarkResult(this.mean, this.median, this.stdDev, this.allTimes);
+}
+
+/// Base class for sorting benchmarks with dataset generation.
+abstract class SortBenchmarkBase extends BenchmarkBase {
+ final int size;
+ late final List<List<int>> _datasets;
+ int _iteration = 0;
+ int _checksum = 0;
+
+ SortBenchmarkBase(super.name, this.size);
+
+ /// Generate datasets for this benchmark condition.
+ List<List<int>> generateDatasets();
+
+ @override
+ void setup() {
+ _datasets = generateDatasets();
+ }
+
+ /// Get the next list to sort (creates a copy).
+ List<int> get nextList {
+ final dataset = _datasets[_iteration];
+ _iteration++;
+ if (_iteration == _datasets.length) _iteration = 0;
+ return dataset.toList();
+ }
+
+ /// Update checksum to prevent compiler optimization.
+ void updateChecksum(List<int> list) {
+ sink ^= list.first ^ list.last ^ list[list.length >> 1] ^ _checksum++;
+ }
+
+ /// The core sorting operation to benchmark.
+ void performSort();
+
+ @override
+ void run() => performSort();
+}
+
+/// Data pattern generators for consistent testing.
+class DatasetGenerators {
+ /// Generate random integer lists.
+ static List<List<int>> random(int size, {int count = 128, int? seed}) {
+ final r = Random(seed ?? 12345);
+ return List.generate(
+ count, (_) => List.generate(size, (_) => r.nextInt(size)));
+ }
+
+ /// Generate sorted lists.
+ static List<List<int>> sorted(int size) {
+ return [List.generate(size, (i) => i, growable: true)];
+ }
+
+ /// Generate reverse-sorted lists.
+ static List<List<int>> reverse(int size) {
+ return [List.generate(size, (i) => size - i - 1, growable: true)];
+ }
+
+ /// Generate lists with few unique values.
+ static List<List<int>> fewUnique(int size,
+ {int uniqueCount = 7, int count = 128, int? seed}) {
+ final r = Random(seed ?? 67890);
+ return List.generate(
+ count, (_) => List.generate(size, (_) => r.nextInt(uniqueCount)));
+ }
+
+ /// Generate pathological input (worst-case for naive quicksort).
+ /// Contains even-indexed elements followed by odd-indexed in reverse.
+ static List<List<int>> pathological(int size) {
+ final sorted = List.generate(size, (i) => i, growable: false);
+ final secondLoopStart = (size - 1).isOdd ? size - 1 : size - 2;
+ final pathological = [
+ for (var i = 0; i < size; i += 2) sorted[i],
+ for (var i = secondLoopStart; i > -1; i -= 2) sorted[i],
+ ];
+ return [pathological];
+ }
+
+ /// Generate nearly sorted lists (only a few elements out of place).
+ static List<List<int>> nearlySorted(int size,
+ {double swapPercent = 0.05, int count = 128, int? seed}) {
+ final r = Random(seed ?? 11111);
+ return List.generate(count, (_) {
+ final list = List.generate(size, (i) => i, growable: true);
+ final numSwaps = (size * swapPercent).round();
+ for (var i = 0; i < numSwaps; i++) {
+ final idx1 = r.nextInt(size);
+ final idx2 = r.nextInt(size);
+ final temp = list[idx1];
+ list[idx1] = list[idx2];
+ list[idx2] = temp;
+ }
+ return list;
+ });
+ }
+}
+
+/// Run a benchmark multiple times and collect statistics.
+BenchmarkResult runBenchmark(SortBenchmarkBase benchmark, int samples) {
+ final times = <int>[];
+
+ // Setup datasets
+ benchmark.setup();
+
+ // Warmup runs (not timed)
+ for (var i = 0; i < 3; i++) {
+ benchmark.run();
+ }
+
+ // Timed runs
+ for (var i = 0; i < samples; i++) {
+ final stopwatch = Stopwatch()..start();
+ benchmark.run();
+ stopwatch.stop();
+ times.add(stopwatch.elapsedMicroseconds);
+ }
+
+ times.sort();
+ final mean = times.reduce((a, b) => a + b) / samples;
+ final median = times[samples >> 1];
+
+ // Calculate standard deviation
+ final variance =
+ times.map((t) => pow(t - mean, 2)).reduce((a, b) => a + b) / samples;
+ final stdDev = sqrt(variance);
+
+ return BenchmarkResult(mean, median, stdDev, times);
+}
+
+/// Print benchmark results as a markdown table.
+///
+/// [baselineName] and [comparisonName] are the labels for the
+/// two implementations
+/// being compared (e.g., "Legacy", "pdqsort", "MergeSort", etc.).
+void printResultsAsMarkdownTable(
+ Map<String, (BenchmarkResult, BenchmarkResult)> results, int size,
+ {required String baselineName,
+ required String comparisonName,
+ bool showStdDev = false}) {
+ final separator = '=' * 100;
+ print('\n$separator');
+ print('Benchmark Results (Size: $size): $comparisonName vs. $baselineName');
+ print(separator);
+
+ // Calculate dynamic column widths based on name lengths
+ final baselineColWidth = max(baselineName.length + 5, 13);
+ final comparisonColWidth = max(comparisonName.length + 5, 13);
+
+ final baselineHeader = '$baselineName (µs)'.padRight(baselineColWidth);
+ final comparisonHeader = '$comparisonName (µs)'.padRight(comparisonColWidth);
+
+ if (showStdDev) {
+ print(
+ '''| Data Condition | $baselineHeader | $comparisonHeader | Improvement | StdDev |''');
+ print(
+ '''| :------------------ | :${'-' * (baselineColWidth - 2)}: | :${'-' * (comparisonColWidth - 2)}: | :---------: | :-----------: |''');
+ } else {
+ print(
+ '''| Data Condition | $baselineHeader | $comparisonHeader | Improvement | Winner |''');
+ print(
+ '''| :------------------ | :${'-' * (baselineColWidth - 2)}: | :${'-' * (comparisonColWidth - 2)}: | :---------: | :-------------: |''');
+ }
+
+ print(
+ '''| **Mean** | ${' ' * baselineColWidth} | ${' ' * comparisonColWidth} | | |''');
+
+ for (final entry in results.entries) {
+ final condition = entry.key;
+ final (baseline, comparison) = entry.value;
+
+ final improvement = (baseline.mean - comparison.mean) / baseline.mean * 100;
+ final improvementString =
+ '${improvement > 0 ? '+' : ''}${improvement.toStringAsFixed(2)}%';
+ final baselineMean = baseline.mean.round().toString();
+ final comparisonMean = comparison.mean.round().toString();
+
+ if (showStdDev) {
+ final stdDevString =
+ '${baseline.stdDev.round()}/${comparison.stdDev.round()}';
+ print(
+ '''| ${condition.padRight(19)} | ${baselineMean.padLeft(baselineColWidth)} | ${comparisonMean.padLeft(comparisonColWidth)} | ${improvementString.padLeft(11)} | ${stdDevString.padLeft(13)} |''');
+ } else {
+ final winner = improvement > 0 ? '$comparisonName 🚀' : baselineName;
+ print(
+ '''| ${condition.padRight(19)} | ${baselineMean.padLeft(baselineColWidth)} | ${comparisonMean.padLeft(comparisonColWidth)} | ${improvementString.padLeft(11)} | ${winner.padLeft(15)} |''');
+ }
+ }
+
+ print(
+ '''| **Median** | ${' ' * baselineColWidth} | ${' ' * comparisonColWidth} | | |''');
+
+ for (final entry in results.entries) {
+ final condition = entry.key;
+ final (baseline, comparison) = entry.value;
+
+ final improvement =
+ (baseline.median - comparison.median) / baseline.median * 100;
+ final improvementString =
+ '${improvement > 0 ? '+' : ''}${improvement.toStringAsFixed(2)}%';
+ final baselineMedian = baseline.median.toString();
+ final comparisonMedian = comparison.median.toString();
+
+ if (showStdDev) {
+ print(
+ '''| ${condition.padRight(19)} | ${baselineMedian.padLeft(baselineColWidth)} | ${comparisonMedian.padLeft(comparisonColWidth)} | ${improvementString.padLeft(11)} | ${' '.padLeft(13)} |''');
+ } else {
+ final winner = improvement > 0 ? '$comparisonName 🚀' : baselineName;
+ print(
+ '''| ${condition.padRight(19)} | ${baselineMedian.padLeft(baselineColWidth)} | ${comparisonMedian.padLeft(comparisonColWidth)} | ${improvementString.padLeft(11)} | ${winner.padLeft(15)} |''');
+ }
+ }
+
+ print(separator);
+}
diff --git a/pkgs/collection/benchmark/legacy_quicksort.dart b/pkgs/collection/benchmark/legacy_quicksort.dart
new file mode 100644
index 0000000..e27f468
--- /dev/null
+++ b/pkgs/collection/benchmark/legacy_quicksort.dart
@@ -0,0 +1,122 @@
+/// Legacy quickSort implementation preserved for benchmarking purposes.
+/// This code is ONLY for benchmarking and should not be used in production.
+library;
+
+import 'dart:math';
+import 'package:collection/src/utils.dart';
+
+/// Performs an insertion sort into a potentially different list than the
+/// one containing the original values.
+///
+/// It will work in-place as well.
+void _movingInsertionSort<E, K>(
+ List<E> list,
+ K Function(E element) keyOf,
+ int Function(K, K) compare,
+ int start,
+ int end,
+ List<E> target,
+ int targetOffset,
+) {
+ var length = end - start;
+ if (length == 0) return;
+ target[targetOffset] = list[start];
+ for (var i = 1; i < length; i++) {
+ var element = list[start + i];
+ var elementKey = keyOf(element);
+ var min = targetOffset;
+ var max = targetOffset + i;
+ while (min < max) {
+ var mid = min + ((max - min) >> 1);
+ if (compare(elementKey, keyOf(target[mid])) < 0) {
+ max = mid;
+ } else {
+ min = mid + 1;
+ }
+ }
+ target.setRange(min + 1, targetOffset + i + 1, target, min);
+ target[min] = element;
+ }
+}
+
+/// Sort [elements] using a quick-sort algorithm.
+///
+/// The elements are compared using [compare] on the elements.
+/// If [start] and [end] are provided, only that range is sorted.
+///
+/// Uses insertion sort for smaller sublists.
+void quickSort<E>(
+ List<E> elements,
+ int Function(E a, E b) compare, [
+ int start = 0,
+ int? end,
+]) {
+ end = RangeError.checkValidRange(start, end, elements.length);
+ _quickSort<E, E>(elements, identity, compare, Random(), start, end);
+}
+
+/// Sort [list] using a quick-sort algorithm.
+///
+/// The elements are compared using [compare] on the value provided by [keyOf]
+/// on the element.
+/// If [start] and [end] are provided, only that range is sorted.
+///
+/// Uses insertion sort for smaller sublists.
+void quickSortBy<E, K>(
+ List<E> list,
+ K Function(E element) keyOf,
+ int Function(K a, K b) compare, [
+ int start = 0,
+ int? end,
+]) {
+ end = RangeError.checkValidRange(start, end, list.length);
+ _quickSort(list, keyOf, compare, Random(), start, end);
+}
+
+void _quickSort<E, K>(
+ List<E> list,
+ K Function(E element) keyOf,
+ int Function(K a, K b) compare,
+ Random random,
+ int start,
+ int end,
+) {
+ const minQuickSortLength = 24;
+ var length = end - start;
+ while (length >= minQuickSortLength) {
+ var pivotIndex = random.nextInt(length) + start;
+ var pivot = list[pivotIndex];
+ var pivotKey = keyOf(pivot);
+ var endSmaller = start;
+ var startGreater = end;
+ var startPivots = end - 1;
+ list[pivotIndex] = list[startPivots];
+ list[startPivots] = pivot;
+ while (endSmaller < startPivots) {
+ var current = list[endSmaller];
+ var relation = compare(keyOf(current), pivotKey);
+ if (relation < 0) {
+ endSmaller++;
+ } else {
+ startPivots--;
+ var currentTarget = startPivots;
+ list[endSmaller] = list[startPivots];
+ if (relation > 0) {
+ startGreater--;
+ currentTarget = startGreater;
+ list[startPivots] = list[startGreater];
+ }
+ list[currentTarget] = current;
+ }
+ }
+ if (endSmaller - start < end - startGreater) {
+ _quickSort(list, keyOf, compare, random, start, endSmaller);
+ start = startGreater;
+ } else {
+ _quickSort(list, keyOf, compare, random, startGreater, end);
+ end = endSmaller;
+ }
+ length = end - start;
+ }
+ _movingInsertionSort<E, K>(list, keyOf, compare, start, end, list, start);
+}
diff --git a/pkgs/collection/benchmark/sort_benchmark.dart b/pkgs/collection/benchmark/sort_benchmark.dart
new file mode 100644
index 0000000..d76f9aa
--- /dev/null
+++ b/pkgs/collection/benchmark/sort_benchmark.dart
@@ -0,0 +1,243 @@
+// Copyright (c) 2025, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/// Benchmarks comparing the new pdqsort implementation against the baseline.
+/// This code is ONLY for benchmarking and should not be used in production.
+library;
+
+import 'package:collection/src/algorithms.dart' show quickSort;
+import 'benchmark_utils.dart';
+import 'legacy_quicksort.dart' as legacy;
+
+// --- Legacy Benchmarks (Old quickSort) ---
+
+class LegacyRandomBenchmark extends SortBenchmarkBase {
+ LegacyRandomBenchmark(int size) : super('Legacy.Random', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.random(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ legacy.quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class LegacySortedBenchmark extends SortBenchmarkBase {
+ LegacySortedBenchmark(int size) : super('Legacy.Sorted', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.sorted(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ legacy.quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class LegacyReverseBenchmark extends SortBenchmarkBase {
+ LegacyReverseBenchmark(int size) : super('Legacy.Reverse', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.reverse(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ legacy.quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class LegacyFewUniqueBenchmark extends SortBenchmarkBase {
+ LegacyFewUniqueBenchmark(int size) : super('Legacy.FewUnique', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.fewUnique(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ legacy.quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class LegacyPathologicalBenchmark extends SortBenchmarkBase {
+ LegacyPathologicalBenchmark(int size) : super('Legacy.Pathological', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.pathological(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ legacy.quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class LegacyNearlySortedBenchmark extends SortBenchmarkBase {
+ LegacyNearlySortedBenchmark(int size) : super('Legacy.NearlySorted', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.nearlySorted(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ legacy.quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+// --- Enhancement Benchmarks (New pdqsort) ---
+
+class EnhancementRandomBenchmark extends SortBenchmarkBase {
+ EnhancementRandomBenchmark(int size) : super('Enhancement.Random', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.random(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class EnhancementSortedBenchmark extends SortBenchmarkBase {
+ EnhancementSortedBenchmark(int size) : super('Enhancement.Sorted', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.sorted(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class EnhancementReverseBenchmark extends SortBenchmarkBase {
+ EnhancementReverseBenchmark(int size) : super('Enhancement.Reverse', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.reverse(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class EnhancementFewUniqueBenchmark extends SortBenchmarkBase {
+ EnhancementFewUniqueBenchmark(int size)
+ : super('Enhancement.FewUnique', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.fewUnique(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class EnhancementPathologicalBenchmark extends SortBenchmarkBase {
+ EnhancementPathologicalBenchmark(int size)
+ : super('Enhancement.Pathological', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.pathological(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+class EnhancementNearlySortedBenchmark extends SortBenchmarkBase {
+ EnhancementNearlySortedBenchmark(int size)
+ : super('Enhancement.NearlySorted', size);
+
+ @override
+ List<List<int>> generateDatasets() => DatasetGenerators.nearlySorted(size);
+
+ @override
+ void performSort() {
+ final list = nextList;
+ quickSort(list, (a, b) => a.compareTo(b));
+ updateChecksum(list);
+ }
+}
+
+// --- Main ---
+
+void main(List<String> args) {
+ const samples = 12;
+
+ // Support multiple sizes via command-line args or use default
+ final sizes = args.isEmpty ? [50000] : args.map(int.parse).toList();
+
+ for (final size in sizes) {
+ print('\n${'=' * 80}');
+ print('Running benchmarks with size: $size');
+ print('=' * 80);
+
+ final benchmarks = [
+ ('Random', LegacyRandomBenchmark(size), EnhancementRandomBenchmark(size)),
+ ('Sorted', LegacySortedBenchmark(size), EnhancementSortedBenchmark(size)),
+ (
+ 'Reverse Sorted',
+ LegacyReverseBenchmark(size),
+ EnhancementReverseBenchmark(size)
+ ),
+ (
+ 'Few Unique',
+ LegacyFewUniqueBenchmark(size),
+ EnhancementFewUniqueBenchmark(size)
+ ),
+ (
+ 'Nearly Sorted',
+ LegacyNearlySortedBenchmark(size),
+ EnhancementNearlySortedBenchmark(size)
+ ),
+ (
+ 'Pathological',
+ LegacyPathologicalBenchmark(size),
+ EnhancementPathologicalBenchmark(size)
+ ),
+ ];
+
+ final results = <String, (BenchmarkResult, BenchmarkResult)>{};
+
+ print('Running benchmarks ($samples samples each)...');
+ for (final (condition, legacy, enhancement) in benchmarks) {
+ print(' Testing $condition...');
+ final legacyResult = runBenchmark(legacy, samples);
+ final enhancementResult = runBenchmark(enhancement, samples);
+ results[condition] = (legacyResult, enhancementResult);
+ }
+
+ printResultsAsMarkdownTable(
+ results,
+ size,
+ baselineName: 'Legacy',
+ comparisonName: 'pdqsort',
+ );
+ }
+}
diff --git a/pkgs/collection/lib/src/algorithms.dart b/pkgs/collection/lib/src/algorithms.dart
index 88d1c4f..70430b9 100644
--- a/pkgs/collection/lib/src/algorithms.dart
+++ b/pkgs/collection/lib/src/algorithms.dart
@@ -482,12 +482,10 @@
);
}
-/// Sort [elements] using a quick-sort algorithm.
+/// Sorts a list between [start] (inclusive) and [end] (exclusive).
///
-/// The elements are compared using [compare] on the elements.
-/// If [start] and [end] are provided, only that range is sorted.
-///
-/// Uses insertion sort for smaller sublists.
+/// The sorting algorithm is a Pattern-defeating Quicksort (pdqsort), a
+/// hybrid of Quicksort, Heapsort, and Insertion Sort.
void quickSort<E>(
List<E> elements,
int Function(E a, E b) compare, [
@@ -495,71 +493,392 @@
int? end,
]) {
end = RangeError.checkValidRange(start, end, elements.length);
- _quickSort<E, E>(elements, identity, compare, Random(), start, end);
+ if (end - start < 2) return;
+ _pdqSortImpl(elements, compare, start, end, _log2(end - start));
}
-/// Sort [list] using a quick-sort algorithm.
+/// Sorts a list between [start] (inclusive) and [end] (exclusive) by key.
///
-/// The elements are compared using [compare] on the value provided by [keyOf]
-/// on the element.
-/// If [start] and [end] are provided, only that range is sorted.
-///
-/// Uses insertion sort for smaller sublists.
+/// Elements are ordered by the [compare] function applied to the result of
+/// the [keyOf] function.
void quickSortBy<E, K>(
- List<E> list,
+ List<E> elements,
K Function(E element) keyOf,
int Function(K a, K b) compare, [
int start = 0,
int? end,
]) {
- end = RangeError.checkValidRange(start, end, list.length);
- _quickSort(list, keyOf, compare, Random(), start, end);
+ end = RangeError.checkValidRange(start, end, elements.length);
+ if (end - start < 2) return;
+ _pdqSortByImpl(elements, keyOf, compare, start, end, _log2(end - start));
}
-void _quickSort<E, K>(
- List<E> list,
- K Function(E element) keyOf,
- int Function(K a, K b) compare,
- Random random,
- int start,
- int end,
-) {
- const minQuickSortLength = 24;
- var length = end - start;
- while (length >= minQuickSortLength) {
- var pivotIndex = random.nextInt(length) + start;
- var pivot = list[pivotIndex];
- var pivotKey = keyOf(pivot);
- var endSmaller = start;
- var startGreater = end;
- var startPivots = end - 1;
- list[pivotIndex] = list[startPivots];
- list[startPivots] = pivot;
- while (endSmaller < startPivots) {
- var current = list[endSmaller];
- var relation = compare(keyOf(current), pivotKey);
- if (relation < 0) {
- endSmaller++;
+/// Minimum list size below which pdqsort uses insertion sort.
+const int _pdqInsertionSortThreshold = 32;
+
+/// Computes the base-2 logarithm of [n].
+///
+/// Uses bitLength to compute the floor(log2(n)) efficiently.
+/// For n == 0 we return 0.
+int _log2(int n) => n > 0 ? n.bitLength - 1 : 0;
+
+// ==========================================
+// Implementation: Direct Comparison
+// ==========================================
+
+void _pdqSortImpl<E>(List<E> elements, int Function(E, E) compare, int start,
+ int end, int badAllowed) {
+ while (true) {
+ final size = end - start;
+ if (size < _pdqInsertionSortThreshold) {
+ _insertionSort(elements, compare, start, end);
+ return;
+ }
+
+ if (_handlePresorted(elements, compare, start, end)) return;
+
+ if (badAllowed == 0) {
+ _heapSort(elements, compare, start, end);
+ return;
+ }
+
+ final mid = start + size ~/ 2;
+ _selectPivot(elements, compare, start, mid, end, size);
+
+ final pivot = elements[start];
+ var less = start;
+ var equal = start + 1;
+ var greater = end;
+
+ while (equal < greater) {
+ final element = elements[equal];
+ final comparison = compare(element, pivot);
+
+ if (comparison < 0) {
+ elements[equal] = elements[less];
+ elements[less] = element;
+ less++;
+ equal++;
+ } else if (comparison > 0) {
+ greater--;
+ elements[equal] = elements[greater];
+ elements[greater] = element;
} else {
- startPivots--;
- var currentTarget = startPivots;
- list[endSmaller] = list[startPivots];
- if (relation > 0) {
- startGreater--;
- currentTarget = startGreater;
- list[startPivots] = list[startGreater];
- }
- list[currentTarget] = current;
+ equal++;
}
}
- if (endSmaller - start < end - startGreater) {
- _quickSort(list, keyOf, compare, random, start, endSmaller);
- start = startGreater;
- } else {
- _quickSort(list, keyOf, compare, random, startGreater, end);
- end = endSmaller;
+
+ if ((less - start) < size ~/ 8 || (end - greater) < size ~/ 8) {
+ badAllowed--;
}
- length = end - start;
+
+ if (less - start < end - greater) {
+ _pdqSortImpl(elements, compare, start, less, badAllowed);
+ start = greater;
+ } else {
+ _pdqSortImpl(elements, compare, greater, end, badAllowed);
+ end = less;
+ }
}
- _movingInsertionSort<E, K>(list, keyOf, compare, start, end, list, start);
+}
+
+bool _handlePresorted<E>(
+ List<E> elements, int Function(E, E) compare, int start, int end) {
+ if (compare(elements[start], elements[start + 1]) > 0) {
+ // Check strictly decreasing
+ var i = start + 1;
+ while (i < end && compare(elements[i - 1], elements[i]) >= 0) {
+ i++;
+ }
+ if (i == end) {
+ _reverseRange(elements, start, end);
+ return true;
+ }
+ } else {
+ // Check non-decreasing
+ var i = start + 1;
+ while (i < end && compare(elements[i - 1], elements[i]) <= 0) {
+ i++;
+ }
+ if (i == end) return true;
+ }
+ return false;
+}
+
+void _reverseRange<E>(List<E> elements, int start, int end) {
+ var left = start;
+ var right = end - 1;
+ while (left < right) {
+ final temp = elements[left];
+ elements[left] = elements[right];
+ elements[right] = temp;
+ left++;
+ right--;
+ }
+}
+
+void _insertionSort<E>(
+ List<E> elements, int Function(E, E) compare, int start, int end) {
+ for (var i = start + 1; i < end; i++) {
+ var current = elements[i];
+ var j = i - 1;
+ while (j >= start && compare(elements[j], current) > 0) {
+ elements[j + 1] = elements[j];
+ j--;
+ }
+ elements[j + 1] = current;
+ }
+}
+
+void _heapSort<E>(
+ List<E> elements, int Function(E, E) compare, int start, int end) {
+ final n = end - start;
+ for (var i = n ~/ 2 - 1; i >= 0; i--) {
+ _siftDown(elements, compare, i, n, start);
+ }
+ for (var i = n - 1; i > 0; i--) {
+ final temp = elements[start];
+ elements[start] = elements[start + i];
+ elements[start + i] = temp;
+ _siftDown(elements, compare, 0, i, start);
+ }
+}
+
+void _siftDown<E>(
+ List<E> elements, int Function(E, E) compare, int i, int n, int start) {
+ var root = i;
+ while (true) {
+ final left = 2 * root + 1;
+ if (left >= n) break;
+ var largest = root;
+ if (compare(elements[start + left], elements[start + largest]) > 0) {
+ largest = left;
+ }
+ final right = left + 1;
+ if (right < n &&
+ compare(elements[start + right], elements[start + largest]) > 0) {
+ largest = right;
+ }
+ if (largest == root) break;
+ final temp = elements[start + root];
+ elements[start + root] = elements[start + largest];
+ elements[start + largest] = temp;
+ root = largest;
+ }
+}
+
+void _selectPivot<E>(List<E> elements, int Function(E, E) compare, int start,
+ int mid, int end, int size) {
+ if (size > 80) {
+ final s = size ~/ 8;
+ _sort3(elements, compare, start, start + s, start + 2 * s);
+ _sort3(elements, compare, mid - s, mid, mid + s);
+ _sort3(elements, compare, end - 1 - 2 * s, end - 1 - s, end - 1);
+ _sort3(elements, compare, start + s, mid, end - 1 - s);
+ } else {
+ _sort3(elements, compare, start, mid, end - 1);
+ }
+ final temp = elements[start];
+ elements[start] = elements[mid];
+ elements[mid] = temp;
+}
+
+void _sort3<E>(
+ List<E> elements, int Function(E, E) compare, int a, int b, int c) {
+ if (compare(elements[a], elements[b]) > 0) {
+ final t = elements[a];
+ elements[a] = elements[b];
+ elements[b] = t;
+ }
+ if (compare(elements[b], elements[c]) > 0) {
+ final t = elements[b];
+ elements[b] = elements[c];
+ elements[c] = t;
+ if (compare(elements[a], elements[b]) > 0) {
+ final t2 = elements[a];
+ elements[a] = elements[b];
+ elements[b] = t2;
+ }
+ }
+}
+
+// ==========================================
+// Implementation: Keyed Comparison (By)
+// ==========================================
+
+/// [badAllowed] tracks how many bad pivot selections are allowed before
+/// falling back to heap sort.
+void _pdqSortByImpl<E, K>(List<E> elements, K Function(E) keyOf,
+ int Function(K, K) compare, int start, int end, int badAllowed) {
+ while (true) {
+ final size = end - start;
+ if (size < _pdqInsertionSortThreshold) {
+ _insertionSortBy(elements, keyOf, compare, start, end);
+ return;
+ }
+
+ if (_handlePresortedBy(elements, keyOf, compare, start, end)) return;
+
+ if (badAllowed == 0) {
+ _heapSortBy(elements, keyOf, compare, start, end);
+ return;
+ }
+
+ final mid = start + size ~/ 2;
+ _selectPivotBy(elements, keyOf, compare, start, mid, end, size);
+
+ final pivotElement = elements[start];
+ final pivotKey = keyOf(pivotElement);
+
+ var less = start;
+ var equal = start + 1;
+ var greater = end;
+
+ while (equal < greater) {
+ final element = elements[equal];
+ final elementKey = keyOf(element);
+ final comparison = compare(elementKey, pivotKey);
+
+ if (comparison < 0) {
+ elements[equal] = elements[less];
+ elements[less] = element;
+ less++;
+ equal++;
+ } else if (comparison > 0) {
+ greater--;
+ elements[equal] = elements[greater];
+ elements[greater] = element;
+ } else {
+ equal++;
+ }
+ }
+
+ if ((less - start) < size ~/ 8 || (end - greater) < size ~/ 8) {
+ badAllowed--;
+ }
+
+ if (less - start < end - greater) {
+ _pdqSortByImpl(elements, keyOf, compare, start, less, badAllowed);
+ start = greater;
+ } else {
+ _pdqSortByImpl(elements, keyOf, compare, greater, end, badAllowed);
+ end = less;
+ }
+ }
+}
+
+bool _handlePresortedBy<E, K>(List<E> elements, K Function(E) keyOf,
+ int Function(K, K) compare, int start, int end) {
+ if (compare(keyOf(elements[start]), keyOf(elements[start + 1])) > 0) {
+ var i = start + 1;
+ while (
+ i < end && compare(keyOf(elements[i - 1]), keyOf(elements[i])) >= 0) {
+ i++;
+ }
+ if (i == end) {
+ _reverseRange(elements, start, end);
+ return true;
+ }
+ } else {
+ var i = start + 1;
+ while (
+ i < end && compare(keyOf(elements[i - 1]), keyOf(elements[i])) <= 0) {
+ i++;
+ }
+ if (i == end) return true;
+ }
+ return false;
+}
+
+void _insertionSortBy<E, K>(List<E> elements, K Function(E) keyOf,
+ int Function(K, K) compare, int start, int end) {
+ for (var i = start + 1; i < end; i++) {
+ final current = elements[i];
+ final currentKey = keyOf(current);
+ var j = i - 1;
+ while (j >= start && compare(keyOf(elements[j]), currentKey) > 0) {
+ elements[j + 1] = elements[j];
+ j--;
+ }
+ elements[j + 1] = current;
+ }
+}
+
+void _heapSortBy<E, K>(List<E> elements, K Function(E) keyOf,
+ int Function(K, K) compare, int start, int end) {
+ final n = end - start;
+ for (var i = n ~/ 2 - 1; i >= 0; i--) {
+ _siftDownBy(elements, keyOf, compare, i, n, start);
+ }
+ for (var i = n - 1; i > 0; i--) {
+ final temp = elements[start];
+ elements[start] = elements[start + i];
+ elements[start + i] = temp;
+ _siftDownBy(elements, keyOf, compare, 0, i, start);
+ }
+}
+
+void _siftDownBy<E, K>(List<E> elements, K Function(E) keyOf,
+ int Function(K, K) compare, int i, int n, int start) {
+ var root = i;
+ while (true) {
+ final left = 2 * root + 1;
+ if (left >= n) break;
+ var largest = root;
+ var largestKey = keyOf(elements[start + largest]);
+
+ final leftKey = keyOf(elements[start + left]);
+ if (compare(leftKey, largestKey) > 0) {
+ largest = left;
+ largestKey = leftKey;
+ }
+
+ final right = left + 1;
+ if (right < n) {
+ final rightKey = keyOf(elements[start + right]);
+ if (compare(rightKey, largestKey) > 0) {
+ largest = right;
+ }
+ }
+ if (largest == root) break;
+ final temp = elements[start + root];
+ elements[start + root] = elements[start + largest];
+ elements[start + largest] = temp;
+ root = largest;
+ }
+}
+
+void _selectPivotBy<E, K>(List<E> elements, K Function(E) keyOf,
+ int Function(K, K) compare, int start, int mid, int end, int size) {
+ if (size > 80) {
+ final s = size ~/ 8;
+ _sort3By(elements, keyOf, compare, start, start + s, start + 2 * s);
+ _sort3By(elements, keyOf, compare, mid - s, mid, mid + s);
+ _sort3By(elements, keyOf, compare, end - 1 - 2 * s, end - 1 - s, end - 1);
+ _sort3By(elements, keyOf, compare, start + s, mid, end - 1 - s);
+ } else {
+ _sort3By(elements, keyOf, compare, start, mid, end - 1);
+ }
+ final temp = elements[start];
+ elements[start] = elements[mid];
+ elements[mid] = temp;
+}
+
+void _sort3By<E, K>(List<E> elements, K Function(E) keyOf,
+ int Function(K, K) compare, int a, int b, int c) {
+ if (compare(keyOf(elements[a]), keyOf(elements[b])) > 0) {
+ final t = elements[a];
+ elements[a] = elements[b];
+ elements[b] = t;
+ }
+ if (compare(keyOf(elements[b]), keyOf(elements[c])) > 0) {
+ final t = elements[b];
+ elements[b] = elements[c];
+ elements[c] = t;
+ if (compare(keyOf(elements[a]), keyOf(elements[b])) > 0) {
+ final t2 = elements[a];
+ elements[a] = elements[b];
+ elements[b] = t2;
+ }
+ }
}
