JavaScript has no sorted containers. I built one for TypeScript.

#opensource #javascript #datastructures #typescript

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, and size-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.