Multiway Powersort

The same node-power merge policy as plain Powersort — only the tree is k-ary instead of binary. Boundary powers are the depth of the shallowest node of a virtual, perfectly balanced k-way tree (i.e. base‑k digits of the run midpoints instead of bits). The run stack is now only weakly increasing, so several runs can share a power; when a smaller power arrives, the whole block of equal-power runs is merged in one go with a single k-way merge (2 to k runs at a time). Fewer, wider merges mean less memory traffic — the win for heavy objects. Pick k below and step through it.

k (merge width) preset mode run lengths (comma-separated)

speed

Press play to run Multiway Powersort.

multiway powersort

 1  def powersort_kway(a, k): 2    n = len(a); i = 0 3    runs = []          # stack; powers weakly increasing 4    j = extend_run(a, i) 5    runs.append((i, j-i, 0)); i = j 6    while i < n: 7      j = extend_run(a, i) 8      p = power_k(runs[-1], (i, j-i), n, k) 9      while runs[-1].power > p:   # strict!10        merge_top_group(a, runs)  # ≤ k-way11      runs.append((i, j-i, p)); i = j12    while len(runs) >= 2:13      merge_top_group(a, runs)

reference (k=4): powersort_4way.h

Note: for clarity this demo uses ascending runs only and skips the minRunLen extension — real implementations also reverse descending runs and pad short runs by insertion sort. The finale here follows the plain policy (merge the top equal-power block repeatedly); production k-way code additionally reshuffles the leftover stack so that almost every finale merge is a full k-way merge.

What changed vs. plain Powersort? Only two things. (1) A boundary's power is the number of leading identical base-k digits of the two run midpoints (plain Powersort uses base 2), so powers index a virtual k-ary tree. (2) The stack invariant relaxes from strictly to weakly increasing: the pop condition becomes top.power > p (strict) instead of >=, so up to k−1 runs can pile up at the same power and are then closed together by a single k-way merge. Everything else — run detection, the near-optimal merge order, stability — is identical. See Multiway Powersort (ALENEX 2023).