{
:list_insertion_on_heap
:list_insertion_on_stack
:list_insertion list_insertion_on_heap
}

Where

Define (list_insertion_on_heap compare input)
    Define (insert sorted a)
        Iterate {left right} From {'nil sorted}
            Match right {
            | 'nil (LIST.reverse [a & left])
            | 'cons.{b right_tail}
                If Pattern 'less Matches (compare a b)
                    (LIST.reverse_append left [a & right])
                    (Continue [b & left] right_tail)
            }
    In
    (LIST.reduce input 'nil insert)

Define (list_insertion_on_stack compare input)
    Define (insert sorted a)
        Unfold sorted
            Match sorted {
            | 'nil [a & 'nil]
            | 'cons.{b sorted_tail}
                If Pattern 'less Matches (compare a b)
                    [a & sorted]
                    [b & (Fold sorted_tail)]
            }
    In
    (LIST.reduce input 'nil insert)

Where

Open LIST {:Infix &}

Where

Let LIST Package "list"