def sort.pass

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

import Base

70# One pass: each two runs merged, in order.
71def sort.pass(
72  ~A: Data,
73  ~le: A -> A -> Bool,
74  +n: Nat,
75  runs: List<&2, List<&2, A>>,
76  out: List<&2, List<&2, A>>
77) -> List<&2, List<&2, A>>:
78  match runs:
79    case Nil{}:
80      List.reverse(&2, List<&2, A>, out)
81    case Con{r, Nil{}}:
82      List.reverse(&2, List<&2, A>, r <> out)
83    case Con{r1, Con{r2, rest}}:
84      sort.pass(~A, ~le, n, rest, List.merge.go(~A, ~le, n, (Nil{}, r1, r2)) <> out)