Task 5 of 5

Payoff: Sort a Real Array

One constraint has been quietly true all along: n must be a power of two. Every thread's partner is its index with one bit flipped, and that only lands inside the array when the array fills the whole index space. Give the network 100 values and threads near the top reach for elements that do not exist — no error, no warning, just a result that is quietly wrong in a way that is very hard to see.

The fix is the one every real implementation uses: pad up to the next power of two with a sentinel that is guaranteed to sort to the end, run the network on the padded array, then slice the padding off. 100 values become 128, sorted, and the last 28 slots come back full of sentinel. Padding costs a little wasted work and buys you an algorithm with no special cases at all.

+Infinity is the textbook sentinel. This task uses a large finite one instead, because a padded array has to survive a round trip through a float texture, and a finite value always does. Anything comfortably above your data's maximum works.

Goal: sort all 100 of values by padding up to a power of two, running the network, and dropping the padding — then log the smallest and largest of the real values.

Requirements

Choose size = the next power of two at or above values.length, and create the kernel with output: [size]
Pad with PAD up to size, run the full stage/stride schedule, then take the first values.length results
console.log the smallest and the largest of the sorted real values — not of the padded array

Hint 1 — the next power of two

Double until you clear the length:

let size = 1;
while (size < values.length) size *= 2;

For 100 values that lands on 128.

Hint 2 — padding and un-padding

Pad before, slice after:

const padded = values.slice();
while (padded.length < size) padded.push(PAD);
// … run the network …
const sorted = Array.from(result).slice(0, values.length);

The sentinels all sort to the end, so the real values keep the front of the array in exactly the right order.

Hint 3 — reading the answer

result[size - 1] is a sentinel, not your largest value. The largest real value is sorted[values.length - 1], after the slice.

Same idea elsewhere

Power-of-two padding is what every production sorter does with this network: CUDA's bitonic samples require it outright and pad in the host code, and library sorts (CUB, rocPRIM, WebGPU's community sort implementations) hide the same padding inside a friendlier signature. The general-case handling never lives in the kernel — it lives in the few lines around it, exactly where you just put it.

All tasks in Bitonic Sort

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.