← All resources

Efficiently sorting gigabytes: the Deferred Merge Sort

Auto-discovered

Blog Advanced

Jelle van der Beek

Visit resource ↗

Description

Efficiently sorting gigabytes: the Deferred Merge Sort is a Superluminal engineering post by Jelle van der Beek on timestamp-ordering huge profiler capture streams with bounded memory.

It motivates out-of-order kernel events from concurrent ringbuffer writers, then reviews external merge I/O costs. The deferred approach stores per-chunk minimum timestamps in a sorted head table, loads and sorts a chunk only when it reaches the front, and often keeps only one or two chunks resident. Prefetch plus background decompress-and-sort hides latency. A hybrid path for wildly unsorted chunks is sketched.

It suits advanced tools programmers building scalable profilers or similar event pipelines. Comfort with external sorting and large binary streams helps.

The write-up is free HTML on Superluminal's site with illustrated walk-throughs of the head-table algorithm.

It shows how near-sorted capture data can make multi-gigabyte global sorts nearly free versus general external merge.