; sort.neb
; an exploration of sorting algorithms in neb

(func .prepend (lst item)
    (list-reverse (append (list-reverse lst) item)))

(func bubble (lst)
    (def orig lst)
    (def working (list))
    (def swp #false)
    (for-count (list-length lst)
        (branch
            ((eq? 0 (list-length (rest orig)))
                (redef working (append working (first orig))))
            ((> (first orig) (first (rest orig)))
                (block
                    (redef swp #true)
                    (redef working (append working (first (rest orig))))
                    (redef orig (.prepend (rest (rest orig)) (first orig)))))
            (#true
                (block
                    (redef working (append working (first orig)))
                    (redef orig (rest orig))))))

    (print (->string working))
    (if swp
        (bubble working)
        working))

(func extend (lst1 lst2)
    (def ret lst1)
    (for-each lst2
        (redef ret (append ret _item_)))
    ret)

(func insert (lst item)
    (extend
        (append (take-while lst (< _item_ item)) item)
        (drop-while lst (< _item_ item))))

(func insertion (lst)
    (def ret (list))
    (for-each lst
        (redef ret (insert ret _item_))
        (print (->string ret)))
    ret)

(func merge (lst)
    (print (concat "sorting: " (->string lst)))
    (if (eq? 1 (list-length lst))
        lst
        (block
            (def half (floor (/ (list-length lst) 2)))
            (def left (merge (slice lst 1 half)))
            (def right (merge (slice lst (+ 1 half))))
            (.merge left right))))

(func .merge (lst1 lst2)
    (print (concat "lst1: " (->string lst1)))
    (print (concat "lst2: " (->string lst2)))
    (def res (list))
    (def w1 lst1)
    (def w2 lst2)
    (while (and (not (empty? w1)) (not (empty? w2)))
        (if (< (first w1) (first w2))
            (block
                (redef res (append res (first w1)))
                (redef w1 (rest w1)))
            (block
                (redef res (append res (first w2)))
                (redef w2 (rest w2)))))
    (while (not (empty? w1))
        (redef res (append res (first w1)))
        (redef w1 (rest w1)))

    (while (not (empty? w2))
        (redef res (append res (first w2)))
        (redef w2 (rest w2)))
    res)