# Payoff: Sort a Real Array

*Task 5 of 5 · [Bitonic Sort](https://gpu.rocks/learn/bitonic-sort-84e0728e.md) · GPU.js Learn*

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

**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:

```js
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:

```js
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.

## Starter code

```js
// 100 values. The network needs a power of two — so give it one.
const gpu = new GPU({ mode });

// TODO: the next power of two at or above values.length (100 → 128).
const size = values.length;

const pass = gpu.createKernel(function (data, stage, stride) {
  const i = this.thread.x;
  const strideBit = Math.floor(i / stride) % 2;
  const dirBit = Math.floor(i / stage) % 2;

  let partner = i - stride;
  if (strideBit === 0) partner = i + stride;

  const me = data[i];
  const other = data[partner];
  if (strideBit === dirBit) return Math.min(me, other);
  return Math.max(me, other);
}, { output: [size] });

// TODO: pad `values` up to `size` with PAD before sorting.
const padded = values.slice();

let result = Float32Array.from(padded);
for (let stage = 2; stage <= size; stage *= 2) {
  for (let stride = stage / 2; stride >= 1; stride /= 2) {
    result = await pass(result, stage, stride);
  }
}

// TODO: drop the padding before reading the answer.
const sorted = Array.from(result);

console.log('smallest:', sorted[0]);
console.log('largest:', sorted[sorted.length - 1]);

const reference = values.slice().sort((a, b) => a - b);
console.log('matches Array.prototype.sort:',
  sorted.length === reference.length &&
  sorted.every((v, i) => Math.abs(v - reference[i]) < 1e-3));
```

---

Interactive version: https://gpu.rocks/learn/bitonic-sort-84e0728e/5

[Previous task](https://gpu.rocks/learn/bitonic-sort-84e0728e/4.md)