How We Ported Python’s natsort to Rust — And the 133,000 Fuzz Inputs That Proved Us Wrong

A post-mortem on building natsort-rs, fixing a 45x performance bug, and catching subtle edge cases with a custom Pytest monkeypatch bridge.

1. Why natsort?
   Porting Python code to Rust using the "Astral playbook" sounds straightforward on paper: rewrite the hot path, compile to native binary, profit. We chose Seth M. Morton’s popular natsort library—a ubiquitous utility for natural sorting (item2 before item10).
   In Python, natsort relies heavily on dynamic typing, tuple-based comparisons, and fallback numeric parsing (try_int, try_float). Translating Python’s dynamic Union[str, int, float] return types into Rust required introducing explicit tagged enums (ParsedComponent) and a hand-crafted Ord trait implementation in key.rs.
   Zero unsafe blocks. Pure memory safety. But getting it to build was only 10% of the battle.

2. The Benchmark That Humbling Us (And the Fix)
   When we ran our first full 10,000-item workload benchmark against Python's natsort, the result was embarrassing:

   • Python natsort: ~0.24s mean
   • Our Compiled Rust Port: ~0.90s mean

   An native binary running nearly 4x slower than interpreted Python was unacceptable.

   The Root Cause: In our initial implementation, natsorted() recompiled the number-matching regular expression from scratch for every single item in the input array. For 10,000 items, we were recompiling regex 10,000 times.

   The Fix: We refactored split.rs to compile the regex once per natsorted() invocation and pass a reference down through the key generation pipeline.

   The Real Result: Latency dropped from ~900ms to ~20ms—shifting our port from 4x slower than Python to 11.8x faster on identical workloads. Disclosing this mistake is important: benchmarking without profiling is just guessing.

3. The Edge Case That Ate Hours: Bare "nan" Tokens
   To prove behavioral equivalence, we didn't just write unit tests—we built a differential fuzz harness (fuzz/differential_fuzz.py) that generated randomized strings, floats, and signs, feeding them simultaneously into real Python natsort and our Rust CLI.
   At iteration 125,000 (REAL mode, Seed 2), the fuzzer flagged a mismatch (1 out of 500 batches / 0.2% failure rate).

   • The Input: A bare text token "nAn" without any accompanying digits.
   • Python's Behavior: Python's parse_string_factory applied try_float() to every split component—even ones that didn't match the numeric regex. Because Python’s float("nan") parses as NaN, Python treated "nAn" as a float and sorted it first under default NaN ordering.
   • Our Rust Port: Our regex splitter only attempted float parsing on substrings containing digits or adjacent signs. It treated "nAn" as plain text, placing it alphabetically amidst text strings.

   The Fix: We rewrote split_into_components_with_regex to split into all pieces (matched and unmatched), uniformly apply float parsing, and insert NUMAFTER-aware separators between adjacent numeric components. We re-ran 133,000+ randomized inputs through the fuzzer across DEFAULT and REAL modes: 0 mismatches.

4. The Pytest Bridge: What Fuzzing Missed
   Fuzzing is great for random input distribution, but structured logic bugs require deterministic tests.
   Instead of re-writing natsort’s test suite in Rust (which risks recreating our own biases), we built a Pytest monkeypatch bridge in tests/original/conftest.py. It intercept calls to natsort.natsorted at module load time and shells out directly to our compiled Rust binary using raw bitmask CLI flags (--alg=).
   This bridge caught two major bugs that 133,000 fuzz items completely missed:

   • The NUMAFTER Leading Placeholder Bug: When an input string started with a number (e.g., "100_apples"), our sequence-alternation logic inserted a hardcoded empty string as a leading placeholder rather than a NUMAFTER-aware sentinel value. This masked NUMAFTER's effect entirely whenever the first component was numeric.
   • Missing PRESORT: ns.PRESORT had zero implementation in our Rust port—an outright missing feature.

   Once both were fixed, running pytest test_natsorted.py directly against the unmodified upstream Python test file yielded 16 passed, 35 honestly skipped (unsupported locale/path flags), 0 failed, and 0 errors.

5. What We Walked Back & Honest Disclosures
   If you want honest numbers over confident claims, here is what natsort-rs does not do:

   • The Unicode Claim Correction: We initially documented that Rust's char::to_digit(10) supported non-ASCII Unicode decimal digits (like Devanagari or Arabic-Indic numerals). A clippy review revealed char::to_digit is strictly ASCII-only at any radix. We updated our documentation to explicitly state ASCII-only numeral support rather than leaving an overclaim standing.
   • Numeric Bounds: We bounded integers to i64 and floats to f64. Numbers exceeding 9.2 × 10¹⁸ fall back gracefully to text comparison rather than arbitrary-precision integer comparisons.
   • Legacy OS Locales: We explicitly skipped ns.LOCALE and os_sorted. Replicating 30-entry legacy OSX/BSD lookup tables or linking against heavy ICU C-libraries added build complexity for non-deterministic OS features.

6. Summary

   • Codebase: 0 unsafe blocks, clean clippy & fmt.
   • Testing: 42 Rust-native tests (including 7 proptest property-based tests verifying Ord transitivity and reflexivity).
   • Parity: 133,000+ fuzz items (0 mismatches) + Upstream Pytest suite bridge (16 passed, 0 failed).
   • Performance: 9–12x speedup over Python.

Check out the code, benchmark methodology, and full 12-section decision log on GitHub:
🔗
GitHub Link
X Link
YouTube Link

Submitted for Hackathon Raptors: Port Mortem 2026 (Track D: Python -> Rust) 🦖