# The Compare-Exchange, as a Gather

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

Quicksort is the wrong algorithm here, and not by a little. How deep it recurses
depends on the data; its partition step writes elements to positions it only discovers as
it goes; and neighbouring threads would take different branches on every comparison. Three
separate ways to be slow. Sorting on a GPU is not a port of a CPU sort — it is a different
algorithm, and this module builds the one GPUs actually use.

It is made of a single move repeated: the **compare-exchange**. Take two
positions, put the smaller value in one and the larger in the other. On a CPU you write
that as a swap. You cannot here — a thread writes exactly one cell, its own. So both
threads of a pair compute their own answer by reading *both* values: the one at the
low index keeps the minimum, the one at the high index keeps the maximum. Same outcome, no
thread ever touching another thread's cell.

Sixteen values, eight pairs: 0 with 1, 2 with 3, and so on. Which of the two you are is
just `this.thread.x % 2`.

## Figures

- **nobody swaps — both threads look at both values and keep their own**

## Goal

**Goal:** make each thread find its partner in the adjacent pair, read
both values, and return the one it should end up holding — minimum at the even index,
maximum at the odd one.

## Requirements

- Work out your partner from `this.thread.x` alone — even indices pair upward, odd indices pair downward
- Read *both* `data[i]` and `data[partner]`
- Return `Math.min` at the even index and `Math.max` at the odd one — never the partner's value unconditionally

## Hint 1 — which half of the pair am I?

`this.thread.x % 2` is 0 for the low member of a pair and 1 for the
high one. Keep it in a variable — but as a *number*, not a comparison: gpu.js
cannot store a boolean in a variable (it compiles in cpu mode and fails to compile in
gpu mode), so write `const side = i % 2;` and test `side === 0`
where you need it.

## Hint 2 — the partner

Start from the downward step and correct it for the low member:

```js
let partner = i - 1;
if (side === 0) partner = i + 1;
```

## Hint 3 — the ending

Both values in hand, the choice is one line each way:

```js
const me = data[i];
const other = data[partner];
if (side === 0) return Math.min(me, other);
return Math.max(me, other);
```

## Same idea elsewhere

Compare-exchange is the primitive every sorting network is built from, and it is
gather-shaped everywhere for the same reason: CUDA's `__shfl_xor_sync` hands a
thread its partner's value so the thread can decide its own result, WGSL and Metal do the
same through subgroup shuffles or threadgroup memory plus a barrier. Nobody writes to
anybody else's slot.

## Starter code

```js
// Eight pairs, sixteen threads. Each thread returns ITS OWN value.
const gpu = new GPU({ mode });

const exchange = gpu.createKernel(function (data) {
  const i = this.thread.x;
  const side = i % 2; // 0 = low member of my pair, 1 = high

  // TODO: work out this thread's partner, read both values, and return
  // the one this thread should hold: min at the low index, max at the high.
  return data[i];
}, { output: [16] });

const result = await exchange(data);
console.log(result);
```

---

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

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