(defn insert [s k]
(let [spl (split-with #(< % k) s)]
(concat (first spl) (list k) (last spl))))
(defn insert-sort [s]
(reduce (fn [s k] (insert s k)) '() s))
(insert-sort (reverse (range 5000)))
throws a stack over flow error. What am I doing wrong here?
Same issue as with Recursive function causing a stack overflow. Concat builds up a bunch of nested lazy sequences like (concat (concat (concat ...))) without doing any actual work, and then when you force the first element all the concat
s must get resolved at once, blowing the stack.