JavaScript ships with Array, Set, and Map — but nothing that keeps its elements sorted as you insert. If you've ever built a leaderboard, an order book, or anything that answers "give me the items between X and Y", you know the workaround: push into an array and .sort() after every insertion. It works, until scale punishes you — you're paying O(n log n) over and over for data that was already 99.9% sorted.
Python solved this years ago with sortedcontainers, built on an elegant "list of lists" design instead of balanced trees. I just published sorted-collections, which brings that idea to TypeScript — with full credit to the original as its inspiration.
What you get
SortedList, SortedSet, SortedMap — always sorted, no manual re-sorting, range queries built in.
O(log n) insertions, O(√n) positional access via sqrt-decomposition into buckets.
Zero runtime dependencies, ~2KB gzip, types included, dual ESM/CJS.- Package quality gated in CI with
publint,arethetypeswrong, andsize-limit.
The API in 30 seconds
import { SortedList, SortedSet, SortedMap } from "sorted-collections";
// SortedList: stays sorted on every insert
const list = new SortedList([5, 1, 4, 2, 3]);
list.add(0);
console.log([...list]); // [0, 1, 2, 3, 4, 5]
console.log(list.at(2)); // 2 — positional access on sorted order
// SortedSet: no duplicates, plus set algebra
const a = new SortedSet([1, 2, 3, 4]);
const b = new SortedSet([3, 4, 5]);
console.log([...a.intersection(b)]); // [3, 4]
// SortedMap: keys always in order, range queries built in
const prices = new SortedMap<number, string>([
[104.5, "order-3"],
[99.2, "order-1"],
[101.0, "order-2"],
]);
for (const [price, id] of prices.irange(100, 105)) {
console.log(price, id); // 101.0 order-2, then 104.5 order-3
}
Custom comparators are fully typed: number and string get natural ordering for free; for your own types, TypeScript requires a comparator at compile time — no silent string-coercion surprises.
Under the hood: buckets, not trees
Instead of a balanced tree of pointer-connected nodes, the data lives in many small contiguous arrays ("buckets"), each internally sorted, with an index of maximums on top. Locating the right bucket is a binary search; the operation itself touches only that small bucket. Contiguous memory is what modern CPUs are good at — that's the bet sortedcontainers made in Python, and it's the same one here.
One consequence of this design worth showing with real numbers: bulk construction. The constructors don't insert element by element — they sort once and slice directly into buckets. Here's bulk vs. per-element construction, in ops/sec (higher is better):
| Structure | n=1,000 | n=100,000 | n=1,000,000 |
|---|---|---|---|
| SortedList | 17,316/s vs 32,250/s | 85/s vs 93/s | 7/s vs 5/s |
| SortedSet | 16,065/s vs 20,200/s | 79/s vs 55/s | 7/s vs 3/s |
| SortedMap | 14,121/s vs 12,476/s | 56/s vs 33/s | 3/s vs 1/s |
An honest reading, because benchmarks that only show wins aren't benchmarks:
SortedMap benefits at every scale, up to 3x faster at one million entries.
SortedSet pulls ahead from ~100,000 elements.
SortedList only wins clearly at the million-element scale — at small and mid sizes, the per-element path is competitive or ahead, and the absolute differences are microseconds.
If you hydrate large datasets — loading a snapshot, rebuilding an index — this is where the design pays off out of the box.
When you should NOT use this
Small datasets, or data you sort once and never touch again: a plain array with .sort() is simpler and probably faster. sorted-collections pays off when you insert and query continuously against data that keeps growing. The docs say this explicitly, with numbers.
Installation
npm install sorted-collections
Works in Node and the browser, ESM or CJS, TypeScript or plain JS.
Reproduce everything
Every number in this post comes from the benchmark script in the repo — one command, fixed seed. If your hardware tells a different story, that's a bug report I want.
This is the library's first public release. Issues and PRs welcome — especially benchmarks I haven't thought of.