johansneirap/sorted-collections
SortedList, SortedSet, and SortedMap for JavaScript/TypeScript — zero runtime dependencies, inspired by Python's sortedcontainers. - johansneirap/sorted-collections
1 stars · 0 forks · TypeScript
README
sorted-collections SortedList, SortedSet, and SortedMap for JavaScript/TypeScript Explore the docs » Report Bug · Request Feature
Table of Contents About The Project Built With Getting Started Prerequisites Installation Usage Performance Roadmap Contributing License Contact Acknowledgments
About The Project JavaScript/TypeScript has no built-in data structure that keeps its elements in sorted order as you mutate it. Common patterns — leaderboards, order books, "give me everything between X and Y" — end up re-sorting an array by hand on every insert, which is O(n log n) repeated: fine for a handful of items, expensive at scale. sorted-collections gives you three structures instead, with zero runtime dependencies and a ~2 KB gzipped bundle (see the badge above for the current, live number):
SortedList — a list that keeps insertion order sorted automatically. SortedSet — a sorted set with no duplicates, plus set-theory operations (union, intersection, difference, isSubsetOf). SortedMap — a dictionary ordered by key.
sorted-collections Array + manual sort native Set/Map Other npm packages in this space Python's sortedcontainers
SortedList ✅ — — Partial coverage, low adoption ✅ (SortedList)
SortedSet ✅ — ✅ unordered Partial coverage, low adoption ✅ (SortedSet)
SortedMap ✅ — ✅ unordered Partial coverage, low adoption ✅ (SortedDict)
Ordered iteration ✅ manual ❌ Varies ✅
Range queries (irange/islice) ✅ manual ❌ Varies ✅
Zero dependencies ✅ ✅ ✅ Varies ✅ (stdlib)
All three are backed by the same "list of lists" (bucketed array) technique Python's sortedcontainers uses — buckets of roughly √n sorted elements, trading a small amount of positional-access speed for a much simpler, easier-to-audit implementation than a balanced tree. See src/internal/bucket-engine.ts for the actual implementation, and Performance for what that trade-off looks like in real numbers. The package is written in TypeScript but designed to be just as comfortable from plain JavaScript — hence no -ts in the name. (back to top) Built With
(back to top)
Getting Started Prerequisites Node.js ^20.19.0 or >=22.12.0. Installation npm i sorted-collections (back to top)
Usage import { SortedList, SortedSet, SortedMap } from 'sorted-collections';
const scores = new SortedList<number>(); scores.add(42); scores.add(7); scores.add(99); [...scores]; // [7, 42, 99]
const tags = new SortedSet<string>(['b', 'a', 'c']); tags.has('b'); // true
const byPrice = new SortedMap<number, string>(); byPrice.set(101.5, 'order-1'); byPrice.set(99.75, 'order-2'); [...byPrice.keys()]; // [99.75, 101.5] Constructing from an existing iterable builds in bulk (sort once, cut into buckets) rather than inserting one element at a time — see Performance for what that's worth at scale. SortedList.from/SortedSet.from/SortedMap.from are equivalent sugar, paralleling Array.from: const scores2 = SortedList.from([42, 7, 99]); // same as new SortedList([42, 7, 99]) Range queries work the same way across all three structures: // Everyone scoring between 50 and 100, inclusive: [...scores.irange(50, 100)];
// Order book: every order priced at 100 or less: [...byPrice.irange(undefined, 100)]; Full API reference and use-case guides (leaderboards, order books, time-series) live at johansneirap.github.io/sorted-collections. (back to top)
Performance Numbers below: Node v25, single run of npm run bench (script in benchmarks/ — reproduce locally with npm run bench; results vary by machine). Ops/sec, higher is better.
Operation SortedList Array (naive)
add(), one at a time, n=5,000 3,146/s 12/s
has(), n=100,000 20,224/s 67/s
Operation SortedSet native Set
add(), one at a time, n=5,000 2,092/s 12,923/s
has(), n=100,000 20,121/s 835,314/s
Operation SortedMap native Map
set(), one at a time, n=5,000 1,397/s 7,056/s
get(), n=100,000 12,453/s 834,080/s
Bulk construction — new SortedX(iterable) sorts once and cuts directly into buckets, instead of inserting one element at a time. Compared against the old per-element path (construct empty, then add()/set() in a loop):
Structure n=1,000 n=100,000 n=1,000,000
SortedList (bulk vs. per-element) 17,316/s vs 32,250/s 85/s vs 93/s 7/s vs 5/s
SortedSet (bulk vs. per-element) 16,065/s vs 20,200/s 79/s vs 55/s 7/s vs 3/s
SortedMap (bulk vs. per-element) 14,121/s vs 12,476/s 56/s vs 33/s 3/s vs 1/s
At n=1,000, SortedList and SortedSet are marginally slower to bulk-construct than the old per-element path — the fixed cost of one Array.prototype.sort() call doesn't have much to amortize over yet, since the bucket size floor (32) already keeps per-element insertion cheap at that scale. The absolute difference is microseconds either way. From ~100,000 elements on, bulk construction wins decisively, up to 3x faster at n=1,000,000. Honest notes — when this library is (and isn't) the right call:
Native Set/Map numbers are a raw-speed reference only, not an apples-to-apples comparison: they don't keep anything sorted, don't offer irange/at/bisectLeft, and iterate in insertion order rather than sorted order. You pay for order; this is what that cost looks like next to not paying for it. add()/set() vs. the naive "array + resort on every insert" pattern is only run up to n=5,000 — that pattern is O(n² log n) and would take minutes at n=100,000. That collapse is the problem this library exists to fix, not an oversight in the benchmark. at(index) and full iteration are O(√n), documented as such — this library deliberately doesn't maintain the extra index a balanced tree would need for O(log n) positional access, favoring a simpler implementation instead. That trade-off costs the most on large collections doing lots of positional lookups; has()/get()/add()/ set() don't pay it.
(back to top)
Roadmap
SortedList, SortedSet, SortedMap implemented, 100% test coverage Property-based tests against naive reference implementations (fast-check) Reproducible benchmark suite Publish 1.0.0 to npm Documentation site (getting started, use-case guides, API reference)
See the open issues for proposed features and known issues. (back to top)
Contributing Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated. See CONTRIBUTING.md for the full guide — environment setup, what a PR needs (tests, a changeset), and code style.
Fork the Project Create your Feature Branch (git checkout -b feature/AmazingFeature) Commit your Changes (git commit -m 'Add some AmazingFeature') Push to the Branch (git push origin feature/AmazingFeature) Open a Pull Request
(back to top)
License Distributed under the MIT License. See LICENSE for more information. (back to top)
Contact Open an issue — bug reports and feature requests both welcome. (back to top)
Acknowledgments
sortedcontainers by Grant Jenks — the Python library this project takes its core "list of lists" technique and naming conventions from. Best-README-Template — the structure this README is based on.
(back to top)