def sort.go

bend-lint-api@0.2.0.0 · shared/lists.bend:86

import Base

86# Passes until one run is left; each pass halves the runs, so `fuel` (the length) is more than enough.
87def sort.go(
88  ~A: Data,
89  ~le: A -> A -> Bool,
90  fuel: Nat,
91  +n: Nat,
92  runs: List<&2, List<&2, A>>
93) -> List<&2, A>:
94  match fuel runs:
95    case _ Nil{}:
96      []
97    case _ Con{r, Nil{}}:
98      r
99    case 0n _:
100      concat(&2, A, runs)
101    case 1n+f _:
102      sort.go(~A, ~le, f, n, sort.pass(~A, ~le, n, runs, []))