Task 1 of 5

The Compare-Exchange, as a Gather

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.

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

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:

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:

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.

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.