# Which Way Does My Pair Sort?

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

Every pass so far sorted every pair the same way. A bitonic network does not, and
that is the whole trick. A sequence that rises and then falls is called **bitonic**,
and a bitonic sequence is the one thing this network can merge into sorted order in log n
passes. So the early passes exist to *build* bitonic runs: neighbouring blocks are
deliberately sorted in opposite directions, so that gluing two of them together gives up
then down.

Which way your block goes is another bit of your index — the one named by
`stage`, the size of the block currently being merged:

```js
const dirBit = Math.floor(i / stage) % 2;   // 0 → my block sorts ascending
```

So a thread now holds two bits. `strideBit` says whether it is the low or the
high member of its pair; `dirBit` says which way its block is sorting. And the
rule is as small as it could be: **keep the smaller value exactly when the two bits
agree.** Low member of an ascending block, or high member of a descending one —
either way, minimum.

One detail makes that legal: `stride` is always smaller than
`stage`, so flipping the stride bit never disturbs the direction bit. Both
members of a pair read the same `dirBit` and agree about which way they are
sorting — without exchanging a word.

## Figures

- **neighbouring blocks sort opposite ways, and your index already knows which**

## Goal

**Goal:** write one full bitonic pass over 8 values — the kernel takes
`(data, stage, stride)` and returns each thread's new value.

## Requirements

- Compute both bits: `strideBit` from `stride`, `dirBit` from `stage`
- The partner still comes from `strideBit`, exactly as in the last task
- Return `Math.min` when the two bits agree and `Math.max` when they differ

## Hint 1 — reading the rule off the table

Four cases, and they collapse to one comparison:

```js
low  + ascending  → min      (0, 0) agree
high + ascending  → max      (1, 0) differ
low  + descending → max      (0, 1) differ
high + descending → min      (1, 1) agree
```

## Hint 2 — the whole body

```js
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);
```

## Same idea elsewhere

Every bitonic implementation on every platform carries this pair of bit tests —
CUDA samples write `(i & k) == 0`, WGSL compute shaders write the same thing
with `&`, and the arithmetic spelling here says exactly the same. What none
of them need is communication: the direction is a property of your index, so a thread can
work it out alone, which is what makes the whole network barrier-free within a pass.

## Starter code

```js
// One pass of the network: (data, stage, stride) in, one value per thread out.
const gpu = new GPU({ mode });

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

  // TODO: work out dirBit from `stage` the same way strideBit comes
  // from `stride`, find your partner, and keep the SMALLER value when
  // the two bits agree.
  let partner = i - stride;
  if (strideBit === 0) partner = i + stride;

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

// stage 2, stride 1: pairs (0,1) and (4,5) sort up, (2,3) and (6,7) sort down.
console.log(await pass(data, 2, 1));
```

---

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

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