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) 
       ((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)) 
             ((left-nonempty (< left-start left-end)) 
              (right-nonempty  (< right-start right-end))) 
            ((and left-nonempty right-nonempty) 
                 ((l (vector-ref from left-start)) 
                  (r (vector-ref from right-start)) 
                  (to-start' (+ to-start 1))) 
               (if (< l r) 
                     (vector-set! to to-start l) 
                     (loop (+ left-start 1) right-start to-start')) 
                     (vector-set! to to-start r) 
                     (loop left-start (+ right-start 1) to-start'))))) 
             (vector-move-left! from left-start left-end to to-start)) 
             (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) 
         (when swap (vector-move-left! from 0 n v 0)) 
         (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)) 
 $ guile ms.scm 
 ; *** checks *** : 409114 correct, 0 failed.