Sorting a Sensor Buffer With No Memory to Spare

Heapsort is the sort to choose when there is no spare memory and every input must finish in O(n log n) time. This example shows that choice being made on a small device, by asking the questions from Choosing a Sort by Memory, Stability and Worst Case in order, and then checks it against quicksort on four inputs.

A sensor node collects 4,096 readings, each a 16-bit integer, into a buffer of 8,192 bytes. Every minute it must sort the buffer to find the median and the top readings before the next batch arrives, and the firmware has less than 1 KB of memory left once the buffer is allocated. Readings arrive in any order, and nothing about the median depends on which of two equal readings comes first.

The memory limit and the deadline decided the answer. Quicksort also sorts in place, and on random data it is usually quicker, so the choice deserves a check. A run sorted 4,096 readings in four arrangements with heapsort and with a textbook quicksort that takes the last item of each range as its pivot, counting comparisons and how deeply the pending ranges nested.

On shuffled readings quicksort made about 30% fewer comparisons. On the other three it made 8,386,560, which is 4,096 × 4,095 ÷ 2, its quadratic worst case, and its ranges nested 4,096 deep: written recursively, that is 4,096 stack frames on a device with less than 1 KB to hold them. A sensor that reports the same value for a minute, such as a thermometer in a steady room, produces exactly the all-equal input. Heapsort stayed under 89,000 comparisons on every input and used no memory beyond a few indices.

What this example shares with Sorting Orders by Date, Then by Customer is that one constraint settled each choice before speed was considered: stability there, memory and the worst case here. Read the constraints first, and the sort usually follows.