(define (vblit v fromv j i end)      ; Blit FROMV[J,END) to V[I,?].
  (let lp ((j j) (i i))
    (vector-set! v i (vector-ref fromv j))
    (let ((j (+ j 1)))
      (if (< j end) (lp j (+ i 1)) ))
    ))


(define (vector-merge! elt< v v1 v2 start start1 end1 start2 end2)

      (cond ((<= end1 start1) 
             (if (< start2 end2) 
                 (vblit v v2 start2 start end2)))

            ((<= end2 start2) 
             (vblit v v1 start1 start end1))
            
            ;; Invariants: I is next index of V to write; X = V1[J]; Y = V2[K].
            (else (let lp ((i start)
                           (j start1) (x (vector-ref v1 start1))
                           (k start2) (y (vector-ref v2 start2)))
                    (let ((i1 (+ i 1)))	; "i+1" is a complex number in R4RS!
                      (if (elt< y x)
                          (let ((k (+ k 1)))
                            (vector-set! v i y)
                            (if (< k end2)
                                (lp i1 j x k (vector-ref v2 k))
                                (vblit v v1 j i1 end1)))
                          (let ((j (+ j 1)))
                            (vector-set! v i x)
                            (if (< j end1)
                                (vblit v v2 k i1 end2)
                                (lp i1 j (vector-ref v1 j) k y)))))))))


(define (vector-merge-sort! elt< v start end tmp)

  (let loop ((start start) (end end))

    (print "start = " start)
    (print "end = " end)
    
    (let ((n (- end start)))

    (cond ((< n 2) (begin))
          
          ((= n 2) 
           (let ((x (vector-ref v start))
                 (y (vector-ref v (+ 1 start))))
             (if (elt< y x)
                 (begin
                   (vector-set! v start y)
                   (vector-set! v (+ 1 start) x)))
             ))

          (else
           (let ((na (quotient (+ n 1) 2)))
             
             (print "na = " na)
             (print "v before = " v)
             (loop start (+ start na))
             (loop (+ start na 1) end)
             (print "v after = " v)

             (let ((x (vector-ref v (+ (- na 1) start)))
                   (y (vector-ref v (+ na start) )))

               (print "x = " x)
               (print "y = " y)
               
               (if (elt< y x)
                   (begin
                     (vblit tmp v start 0 (+ start na))
                     (print "tmp = " tmp)
                     (vector-merge! elt< v tmp v 0 0 na (+ na start) end)
                     ))
               ))
          ))
    ))
)

(define v (vector 1 5 2 7 3 9 4 6))
(define n (vector-length v))
(define tmp (make-vector (quotient (+ 1 n) 2)))

(vector-merge-sort! < v 0 n tmp)

(print v)