C++23 / fixed-width radix sort

Sort the prefix.Move the record.

bsort orders fixed-width binary records by a key prefix. Use it as a memory-mapped command-line tool or link the same engine into C++.

Download source View on GitHub

LGPL 2.0 C++23 Binary + printable ASCII CLI + library

8 B key / 100 B record ascending

03 1A 7F …01

18 C0 22 …02

5B 09 D1 …03

C4 80 0E …04

F9 44 A7 …05

COMPARE KEY PREFIX MOVE FULL RECORD

100 Bdefault fixed record width

8 Bdefault key prefix

314variable-length differential cases

2 pathsin-place or copied output

The useful constraint

Fixed records let the sorter specialize.

General-purpose comparison sorts solve a larger problem. bsort uses the shape you already know—record width, key width, and byte alphabet— to keep partitioning work simple and record movement explicit.

01 / KEY PREFIX

Order only what matters.

Compare the first key_size bytes while preserving every byte of the enclosing record. Key and record lengths vary independently.

02 / MEMORY PATH

Sort in place or copy once.

Map and reorder one file directly, or read one mapping and write another. The library exposes the same choice for memory buffers.

03 / LEAF CLEANUP

Stop radix work at the right size.

Tuned radix cutoffs hand small buckets to cached-key cleanup sorts. Binary and printable-ASCII keys use independently measured defaults.

MSD radix engine

Count. Partition. Recurse only where it pays.

Histograms are reused across recursive passes. Record cycles move data in place, while small leaves switch to a keyed cleanup path rather than paying for another full radix level.

01 / COUNT

Build the histogram

Validate the selected alphabet and count the current key byte in one pass.

02 / PARTITION

Rotate whole records

Place records into byte buckets with bounded scratch storage and push-ahead cycles.

03 / FINISH

Recurse or clean up

Continue on large buckets. Sort small leaves by cached keys and gather each record once.

One engine / two surfaces

Use the binary. Or keep the call in process.

Command line

Sort a file in place, or keep input and output separate. Printable ASCII keys use a compact 95-bucket specialization.

shellin place + copied

$ bsort -r 100 -k 8 records.bin
$ bsort -a -i input.bin -o output.bin

C++ library

Configure the record and key shape, then sort into a separate buffer—or pass the same pointer twice for in-place operation.

C++23bsort::sort_records

bsort::SortConfig config {
  .record_size = 100,
  .key_size = 8,
};
bsort::sort_records(out, in, bytes, config);

Source release

Build it. Check it. Install it.

The source archive includes the command-line tool, static library, public header, tests, CMake package metadata, and the bsort(1) manual page.

Get bsort.tar.gz Browse source

~/src/bsortGNU Make

$ curl -LO https://bsort.goblinreactor.com/bsort.tar.gz
$ tar -xzf bsort.tar.gz
$ cd bsort
$ ./configure --prefix=/usr/local
$ make -j
$ make check
$ sudo make install

Make install → CMake build → Manual page → Report an issue →