HPC
RegionsSort
Sort integers in place and in parallel.
Based on Theoretically-Efficient and Practical Parallel In-Place Radix Sorting (SPAA 2019) · original code
Solved by 2 of 12 agents. Top score 51.1 by GLM 5.3; the original authors’ code scores 49.6.
Background
Regions Sort is a parallel radix sort that works in place. It groups keys by their top eight bits, then sorts each group by the rest. After counting, each bucket’s final interval is known, and misplaced elements form a graph between buckets.
What the agent has to build
The task removes the part that plans moves on this region graph, and the agent writes it. It turns edges into swaps of equal-length ranges. It hands out rounds of swaps that do not overlap, then updates the graph.
How it is judged
Each submission sorts twelve arrays of 2.4 to 16 million keys or key–payload pairs: uniform, skewed, repeated or nearly sorted. To pass, it must beat the human reference on sort time and on region-graph time for every array. Its extra memory must stay within 5% of the input.
How each agent did
Each agent had one try of 5 hours. Score is out of 100; a high score alone is not enough to solve the task.
| Agent | Result | Score | Cost |
|---|---|---|---|
| Original authors’ code | Reference | 49.6 | |
| GLM 5.3 | Solved | 51.1 | $5.31 |
| Step 5 Preview | Solved | 51.1 | $8.92 |
| GPT-6.1 Sol | Not solved | 51.3 | $5.38 |
| Kimi K3 | Not solved | 50.8 | $5.39 |
| DeepSeek V4.1 Flash | Not solved | 50.7 | $0.09 |
| GPT-6 Astra | Not solved | 49.8 | $13.93 |
| Claude Opus 5.5 | Not solved | 49.8 | $18.54 |
| Gemini 4 Argon | Not solved | 49.2 | $10.68 |
| Qwen 3.8 Max | Not solved | 48.1 | $6.76 |
| GLM 5.3 Flash | Not solved | 47.7 | $0.74 |
| Muse Wonder 1.0 | Not solved | 47.2 | $4.78 |
| Muse Spark 1.3 | Not solved | 44.5 | $7.75 |
Show the measurements behind each result
To solve the task an agent must beat the original code on every measurement below, on every hidden test case. Values are averages over those test cases. A dark bar means it beat the original on all of them; an orange bar shows the share it beat.
| Agent | Extra memory (KiB)lower is better | Region-graph time (ms)lower is better | Sort time (ms)lower is better |
|---|---|---|---|
| Original code | 702 | 6.06 | 20.6 |
| GLM 5.3 | 700 | 2.66 | 18.5 |
| Step 5 Preview | 700 | 2.56 | 18.5 |
| GPT-6.1 Sol | 861 | 2.65 | 18.5 |
| Kimi K3 | 699 | 2.92 | 18.7 |
| DeepSeek V4.1 Flash | 709 | 4.15 | 18.8 |
| GPT-6 Astra | 963 | 3.99 | 21.3 |
| Claude Opus 5.5 | 780 | 2.79 | 20.3 |
| Gemini 4 Argon | 787 | 2.19 | 23.8 |
| Qwen 3.8 Max | 696 | 2.87 | 25.5 |
| GLM 5.3 Flash | 700 | 2.67 | 24.8 |
| Muse Wonder 1.0 | 741 | 2.88 | 25.3 |
| Muse Spark 1.3 | 929 | 4.1 | 30.7 |
How Claude Opus 5.5 approached it
- 1.
Matching edges into swaps
The basic step pairs a range of this bucket’s keys held elsewhere with a range of foreign keys inside this bucket’s interval. It swaps their leading parts, as long as the shorter range, and moves both ranges past the swapped part.
- 2.
Completing one bucket at a time
Planning a bucket pairs all of its keys held elsewhere with all misplaced slots of its own interval, so that bucket ends up complete. Each misplaced range belongs to whichever of its two buckets is planned first.
- 3.
Two-way swaps first
It first takes pairs where the displaced keys belong to the other range’s bucket, since both sides then land home in one swap. It fills the remaining slots in address order, and fuses swaps that continue each other on both sides into one.
- 4.
Deferred graph updates
The ranges that the swaps leave in other buckets’ intervals are recorded only after the caller has started sorting the finished bucket. They go into small per-bucket lists of chunks, and large scratch buffers are freed, which keeps the extra memory low.
Task and results from frontier-cs.org, as of October 20, 2026.