Natural sorting of s-expressions in systems that only support lexicographic sorting

Usage no npm install needed!

<script type="module">
  import buckySortkey from 'https://cdn.skypack.dev/bucky-sortkey';


Build Status

This package lets you encode s-expressions like ["foo", ["bar", ["baz"], []]] as special strings, called sort keys, that produce a "natural" sort order when compared using ordinary strcmp() lexicographic comparison. This is useful for example for using s-expressions as keys in a database system that only supports lexicographic comparison.

An s-expression is either:

  • A string of zero or more characters (not containing any NUL \0 characters)
  • A list of zero or more s-expressions

Strings sort before lists, and shorter strings (lists) sort before longer strings (lists) that have the shorter string (list) as prefix.

Here are some sample s-expressions and their sort keys (in increasing order):

expr: "foo"
sort: "foo\0

expr: ["foo","bar"]
sort: ["foo\0"bar\0\0

expr: ["foo",[],["bar"]]
sort: ["foo\0[\0["bar\0\0\0


A string is encoded as: " + string + \0

A list is encoded as: [ + concatenated contents of list + \0

" (ASCII 34) sorts before [ (ASCII 91), so strings automatically come before lists.

Code map