notreally_timsort.janet

(defn insertion-sort [arr left right]
  (for i (+ left 1) (+ right 1)
    (def temp (in arr i))
    (var j (- i 1))
    (while (and (>= j left) (> (in arr j) temp))
           (set (arr (+ j 1)) (in arr j))
           (-- j))

    (set (arr (+ j 1)) temp))
  arr)


(defn merge-arrays [arr left middle right]
  (def len-left (- middle left -1))
  (def len-right (- right middle))
  (def left-side (array/slice arr left (+ left len-left)))
  (def right-side (array/slice arr (+ middle 1) (+ middle len-right 1)))

  (var l 0) 
  (var r 0)
  (var dst left)

  (while (and (< l len-left) (< r len-right))
    (if (<= (in left-side l) (in right-side r))
      (do
        (set (arr dst) (in left-side l))
        (++ l))
      (do
        (set (arr dst) (in right-side r))
        (++ r)))
    (++ dst))

  (while (< l len-left)
       (set (arr dst) (in left-side l))
       (++ l)
       (++ dst)

   (while (< r len-right)
        (set (arr dst) (in right-side r))
        (++ r)
        (++ dst))))
  

(defn timsort [arr]
 (def len (length arr))

 # sort each run with insertion sort.
 (each i (range 0 len 32)
   (insertion-sort arr i (min (+ i 31) (- len 1))))

 (var size 32)

 # merge runs
 (while (< size len)
   (var left 0)
   (while (< left len)
     (def mid (min (+ left size -1) (- len 1)))
     (def right (min (+ left (* 2 size) -1) (- len 1)))
     (merge-arrays arr left mid right)
     (+= left (* 2 size)))
  (*= size 2))
 arr) 
  


(comment
  (def arr @[0 2 4 6 1 3 5 7])
  (merge-arrays arr 0 3 7)
  (pp arr)

  (def arr (range 100))
  (pp (timsort arr))

  (def arr (map (fn [x] (math/random)) (range 100)))
  (pp arr)
  (pp (timsort arr)))


(def test-input (map (fn [x] (math/random)) (range 1000000)))

(def arr1 (array/slice test-input))
(def start (os/clock))
(sort arr1)
(printf "sort(): %.2fsec" (- (os/clock) start))

(def arr2 (array/slice test-input))
(def start (os/clock))
(timsort arr2)
(printf "timsort(): %.2fsec" (- (os/clock) start))