An adaptive sorting engine designed around one core belief: data distributions are not random in practice, and algorithms should exploit that structure instead of ignoring it.
Sherlock Sort detects patterns inside the input, selects the most suitable local strategy, and then composes those local wins into a globally sorted result.
Pipeline:
Scan -> Detect -> Classify -> Adapt -> Execute -> Merge
| Dimension | What Sherlock Sort Delivers |
|---|---|
| Core Idea | Segment-aware adaptive strategy selection |
| Worst-Case Target | O(n log n) behavior profile |
| Practical Edge | Exploits runs, duplicates, low entropy, and compact ranges |
| Governance | Deterministic, threshold-driven, explainable decisions |
| Trust Layer | Unit, edge, stress, fuzz, comparator, and regression checks |
flowchart LR
A[Input Array] --> B[Run Detection]
B --> C[Feature Extraction]
C --> D[Strategy Classification]
D --> E[Segment Execution]
E --> F[K-Way Merge]
F --> G[Globally Sorted Output]
C --> C1[Sortedness]
C --> C2[Duplication Ratio]
C --> C3[Entropy]
C --> C4[Value Range]
Most production systems still default to one-size-fits-all sorting. Sherlock Sort replaces that with an explainable decision system that tailors execution to actual data shape.
Why this is a strong solution:
- Algorithmic leverage over brute force: detects sortedness, duplicates, entropy, and value range before choosing a strategy.
- Practical performance profile: preserves worst-case intent near O(n log n), while unlocking faster paths on structured inputs.
- Explainable behavior: every segment decision is deterministic and traceable through thresholds and strategy mapping.
- Engineering credibility: backed by unit, stress, fuzz, comparator, and regression checks.
- Product readiness: includes benchmarking, trace export, and visualization for demonstration and diagnostics.
This is not just another sorter. It is a framework for adaptive algorithm selection.
Traditional sorting answers one question: "What is the fastest general-purpose algorithm on average?"
Sherlock Sort answers a better question: "Given this specific data, what is the right algorithm right now?"
That shift matters because real datasets often contain:
- monotonic runs
- partial ordering
- duplicate-heavy regions
- compact value ranges
The system captures those signals and routes each segment to the strategy with the highest expected payoff.
For each detected run/segment, Sherlock Sort computes:
- sortedness
- duplication ratio
- entropy estimate
- value range
Default decision model:
- already sorted -> SKIP
- size < 32 -> INSERTION
- duplication ratio > 0.30 and compact range -> COUNTING
- entropy < 0.15 -> MERGE
- otherwise -> QUICKSORT (std::sort fallback)
Decision logic visual:
flowchart TD
S[Segment] --> Q1{Already sorted?}
Q1 -- Yes --> K[SKIP]
Q1 -- No --> Q2{Size < 32?}
Q2 -- Yes --> I[INSERTION]
Q2 -- No --> Q3{Dup ratio > 0.30 and compact range?}
Q3 -- Yes --> C[COUNTING]
Q3 -- No --> Q4{Entropy < 0.15?}
Q4 -- Yes --> M[MERGE]
Q4 -- No --> Q[QUICKSORT]
After segment-level sorting, a k-way merge produces the final global ordering.
Complexity model:
- detection: O(n)
- segment sorting: sum of per-segment strategy costs
- merge: O(n log k), k = number of segments
- design target: O(n log n) worst-case behavior with better practical paths on favorable structure
- Better fit for heterogeneous workloads: avoids penalizing easy regions with unnecessarily expensive logic.
- Explainable optimization: thresholds and strategy decisions are auditable and tunable.
- Modular architecture: strategy layer can evolve (new detectors/heuristics) without rewriting the core pipeline.
- Demonstrable differentiation: event traces and visual playback make the adaptation visible to stakeholders.
flowchart TB
IN[Input] --> CORE[Core Engine]
CORE --> DET[Detection Layer]
CORE --> DEC[Decision Engine]
DEC --> STRAT[Strategy Layer]
STRAT --> EXEC[Execution Engine]
EXEC --> MERGE[Merge Engine]
MERGE --> OUT[Output]
CORE --> MET[Metrics and Logging]
MET --> BENCH[Benchmarking]
MET --> QC[Quality Control]
The repository already includes a quality baseline that reduces deployment risk:
- unit correctness tests
- edge-case tests
- stress tests (including 1M-element scale)
- fuzz/property-style tests
- comparator equivalence checks against std::sort
- performance regression smoke checks
- core/: adaptive engine, detectors, strategy implementations, and utilities
- benchmarks/: benchmark runner, datasets, and result artifacts
- qc/: correctness, fuzz, stress, and regression quality checks
- visualization/: web playback assets and recorded demo frames
- docs/: architecture, complexity, decision model, and design rationale
- examples/: runnable usage examples
- scripts/: convenience automation for tests, benchmarks, and trace generation
Build:
cmake -S . -B build
cmake --build build -jRun examples and benchmark flow:
./build/simple_example
./build/large_dataset
./build/benchmark_runner
./build/known_algorithms_bench
./scripts/generate_charts.py
./scripts/generate_event_trace.shBuild the known algorithm comparison benchmark once:
c++ -std=c++17 -O3 -I. benchmarks/known_algorithms_bench.cpp build/libsherlock_core.a -o build/known_algorithms_benchBenchmark outputs:
- benchmarks/results/results.csv
- benchmarks/results/known_algorithms.csv
- benchmarks/results/charts/
- docs/time_complexity_and_benchmarks.md
Benchmark visualizations:
Run full quality suite:
./scripts/run_all_tests.shPipeline animation:
Interactive viewer:
cd visualization/web
npm install
npm run devIf visualization/web/public/events.json exists, the UI renders real C++ trace events. Otherwise it uses synthetic fallback data for demonstration.
Sherlock Sort currently prioritizes clarity, reproducibility, and benchmarkability over low-level micro-optimizations. That makes it strong for:
- proving the adaptive thesis
- communicating algorithmic value to technical leadership
- providing a clean foundation for future performance tuning
Recent optimization passes reduced benchmark-mode overhead in probing and event reporting, materially improving clustered/random behavior while preserving correctness and route visibility. The main remaining performance gap is the rotated-sorted path, which is the current optimization focus.