(define (merge-vectors a b)
  (merge-loop a b (make-vector (+ (vector-length a) (vector-length b))) 0 0 0))

(define (merge-loop a b c i j k)
  (cond
    [(and (>= i (vector-length a)) (>= j (vector-length b))) c]
    [(>= i (vector-length a)) (vector-set! c k (vector-ref b j)) (merge-loop a b c i (+ j 1) (+ k 1))]
    [(>= j (vector-length b)) (vector-set! c k (vector-ref a i)) (merge-loop a b c (+ i 1) j (+ k 1))]
    [#t (if (<= (vector-ref a i) (vector-ref b j))
            (begin (vector-set! c k (vector-ref a i)) (merge-loop a b c (+ i 1) j (+ k 1)))
            (begin (vector-set! c k (vector-ref b j)) (merge-loop a b c i (+ j 1) (+ k 1))))] ))





(define (merge-sort array)
  (if (< (vector-length array) 2)
      array
      (let [(left  (merge-sort (copy-part array 0 (div (vector-length array) 2))))
            (right (merge-sort (copy-part array (div (vector-length array) 2) (vector-length array))))]
        (merge-vectors left right))))


(define (copy-part array i j)
  (let ([copy (make-vector (- j i))])
    (copy-part-loop array i copy 0)
    copy))

(define (copy-part-loop from i to k)
  (when (< k (vector-length to))
      (vector-set! to k (vector-ref from i))
      (copy-part-loop from (+ i 1) to (+ k 1))))


(display (merge-sort (make-vector 0 )))