# mergsort

Our old friend mergesort.

``` \$ cat ms.scm
(include-from-path "utils.scm")
(include-from-path "srfi-78/srfi-78.scm")
(check-set-mode! 'summary)

(define (mergesort! v)

(define n (vector-length v))

(define (merge! from i to step)
(let*
((left-end (min (+ i step) n))
(right-end (min (+ left-end step) n)))

(let loop ((left-start i) (right-start left-end) (to-start i))

(let
((left-nonempty (< left-start left-end))
(right-nonempty  (< right-start right-end)))

(cond
((and left-nonempty right-nonempty)
(let
((l (vector-ref from left-start))
(r (vector-ref from right-start))
(to-start' (+ to-start 1)))

(if (< l r)
(begin
(vector-set! to to-start l)
(loop (+ left-start 1) right-start to-start'))
(begin
(vector-set! to to-start r)
(loop left-start (+ right-start 1) to-start')))))

(left-nonempty
(vector-move-left! from left-start left-end to to-start))

(right-nonempty
(vector-move-left! from right-start right-end to to-start)))))))

(let loop ((step 1) (from v) (to (make-vector n)) (swap #f))
(if (>= step n)
(begin
(when swap (vector-move-left! from 0 n v 0))
v)
(begin
(do ((i 0 (+ i (* step 2)))) ((>= i n))
(merge! from i to step))
(loop (* step 2) to from (not swap))))))

(define (check-it n)

(define sorted-v (make-identity-vector n))

(call-with-permuted-vector (vector-copy sorted-v)
(lambda (v)
(check (mergesort! (vector-copy v)) => sorted-v))))

(do ((i 0 (+ i 1))) ((>= i 10))
(check-it i))

(check-report)

\$ guile ms.scm

; *** checks *** : 409114 correct, 0 failed.

\$
```