Adaptive Sorting Algorithm

A sort that
learns as it runs

VisionSort builds a probabilistic model of your data's distribution before touching most elements — then predicts where each value belongs, falling back to comparisons only when it isn't sure.

T(n,H)

Complexity

Phases

Tests passing

O(n)

Best case

View on GitHub Read Whitepaper

Live sort visualisation

IDLE — press run

Algorithm step-by-step — real internal operations

IDLE — press Run to trace the algorithm

Core Thesis

Every element touch does two jobs

Existing sorts extract one bit of information per comparison: A > B or A < B. VisionSort extracts two: the element's position, and a model update that sharpens predictions for every element not yet processed.

01 — The Problem

O(n log n) assumes maximum entropy

The comparison sort lower bound holds for uniformly random input. Real-world data — timestamps, prices, IDs — is not uniform. It has structure. It has low entropy. The bound doesn't have to be tight.

02 — The Insight

Vision builds a scene model first

The visual system samples the scene coarsely before examining anything closely. It directs attention toward disorder, not uniformly. VisionSort maps this onto arrays: sample, model, predict, fixate.

03 — The Mechanism

Bayesian updates during placement

Each element placed updates the distribution model. Entropy decays. Anchor points refine. Confidence grows. The 100th element to be sorted costs far less than the 1st — the algorithm accelerates through its own data.

04 — The Result

Cost parameterised by entropy, not size

Complexity is T(n, H) where H is the Shannon entropy of the input. On structured data, H is small and cost is sublinear. On adversarial data, H = log₂(n) and it falls back to O(n log n). You can never be beaten below baseline.

Algorithm

Five phases, one pass

Each phase has a defined cost and a clear output. Phases 1–3 build the picture. Phase 4 does the work — cheapening as it goes. Phase 5 integrates.

PHASE 1

The Glance

O(log² n)

Sample ⌈log₂(n)⌉ evenly-spaced elements. Sort them. These sorted samples become anchor points — a coarse map of where values live across the array. Compute initial entropy from the sample histogram. Cost is essentially free.

PHASE 2

Segmentation

O(n)

Single linear scan. Walk runs to exhaustion and extend them to a minimum of 64 elements (`MINRUN`) using insertion sort before emitting. Descending runs reversed in-place. Guaranteed: segments tile the array with no gaps or overlaps.

PHASE 3

Disorder Mapping

O(k√L)

Score segments on disorder (estimated inversions) and entropy (Shannon histogram). Plot in 2D space. Assign a sort route. Insert into a max-heap by priority. Segments < 128 elements skip scoring and route directly to Trivial.

PHASE 4

Directed Fixation

Decreasing marginal cost

Pop highest-priority segment. Sort via its assigned route. For PlacementSort: assign elements to cache-local buckets via model prediction, sort buckets independently, and verify block boundaries. Update the model after each bucket. Repeat until heap is empty.

PHASE 5

Integration

O(n log k)

Bottom-up pairwise merge of all sorted segments utilizing galloping (exponential search) for fast insertion in nearly-sorted data. Uses a single scratch buffer (1× peak memory overhead) to iteratively ping-pong reads and writes.

Routing

The 2D decision space

Each segment is scored on disorder and entropy independently. The combination determines which of four sort routes is applied. Only one quadrant requires full O(n log n) treatment.

DISORDER (x) × ENTROPY (y) — SEGMENT ROUTING

LOW DISORDER

HIGH DISORDER

LOW ENTROPY

NearlyFree
Verify only
Single pass to confirm order. If no violations found, zero work performed.

PlacementSort

Bucket-local predict

Segment divided into cache-sized buckets based on model predictions. Verified via linear scan.

HIGH ENTROPY

Verify

Confirm order

Scan for violations. Apply insertion sort only if violations found.

FullSort

Introsort fallback

Quicksort with heapsort fallback. Guaranteed O(n log n). The adversarial path.

PERFORMANCE BY INPUT CLASS

Already sorted

O(n)

Nearly sorted (2% swaps)

O(n · H)

Clustered / structured data

O(n · H)

Reversed input

O(n log n)

Uniform random

O(n log n)

Adversarial max-entropy

O(n log n)

200,000 elements — averaged over 12 runs

Input

VisionSort

Quicksort

std::sort

Merge sort

vs Quicksort

Random

29,861μs

21,044μs

11,703μs

35,962μs

-29% slower

Nearly Sorted

5,972μs

8,835μs

5,174μs

13,952μs

WIN +32%

Clustered

30,509μs

20,357μs

8,765μs

30,507μs

-33% slower

Reversed

3,124μs

6,407μs

247μs

13,284μs

WIN +51%

All Same

1,627μs

232μs

187μs

12,308μs

-85% slower

Model confidence over time — the cost curve

Confidence rises as observations accumulate. Each element processed costs less than the last.

Usage

Get started in Rust

VisionSort works on any type that implements PartialOrd + Into<f64> + Copy. All standard numeric types work out of the box.

use visionsort::vision_sort;

fn main() {
    let mut data = vec![3.0_f64, 1.0, 4.0, 1.0, 5.0, 9.0, 2.0, 6.0];
    vision_sort(&mut data);
    println!("{:?}", data);
    // [1.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 9.0]
}

use visionsort::VisionSort;

fn main() {
    let mut data = vec![5.0_f64, 2.0, 8.0, 1.0, 9.0, 3.0];

    let mut sorter = VisionSort::new();
    sorter.sort(&mut data);

    // Inspect the distribution model post-sort
    println!("entropy:      {}", sorter.model.entropy);
    println!("observations: {}", sorter.model.observations);
    println!("anchors:      {:?}", sorter.model.anchors);
}

use visionsort::vision_sort;

// Sort by timestamp — implement Into<f64> on your key
#[derive(Clone, Copy, PartialEq, PartialOrd)]
struct Event {
    timestamp: f64,
    payload: u32,
}

impl Into<f64> for Event {
    fn into(self) -> f64 { self.timestamp }
}

fn main() {
    let mut events = vec![
        Event { timestamp: 1700.0, payload: 42 },
        Event { timestamp: 1500.0, payload: 11 },
    ];
    vision_sort(&mut events);
}

# Cargo.toml

[package]
name = "my-project"
version = "0.1.0"
edition = "2021"

[dependencies]
visionsort = { path = "../visionsort" }

# Then: cargo build
# Then: cargo test   (16 tests, all green)

Distribution model — live state 0 observations

ENTROPY

1.000

Decreasing as model learns

CONFIDENCE

0.000

Increasing with observations

ANCHOR POINTS

Grow in high-surprise regions

ROUTE MIX

—

Dominant route this sort

A sort thatlearns as it runs

Every element touch does two jobs

Five phases, one pass

The 2D decision space

Get started in Rust

A sort that
learns as it runs