SHARE
TWEET

scheme-merge-sort

a guest Dec 28th, 2019 109 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (define (split-in-half lst)
  2.   (let ((left-length (div (length lst) 2)))
  3.     (values (take lst left-length)
  4.             (drop lst left-length))))
  5.  
  6. (define (split-by-less-or-equal n lst)
  7.   (define (do-split lst true-acc false-acc)
  8.     (if (null? lst)
  9.         (values true-acc false-acc)
  10.         (let ((next (car lst))
  11.               (rest (cdr lst)))
  12.           (if (<= next n)
  13.               (do-split rest (append true-acc (list next)) false-acc)
  14.               (do-split rest true-acc (append false-acc (list next)))))))
  15.  
  16.   (do-split lst '() '()))
  17.  
  18. (define (merge left right)
  19.   (define (do-merge left right acc)
  20.     (if (null? left)
  21.         (append acc right)
  22.         (let ((next (car left)))
  23.           (let-values (((less-or-equal greater)
  24.                         (split-by-less-or-equal next right)))
  25.             (do-merge (cdr left)
  26.                       greater
  27.                       (append acc less-or-equal (list next)))))))
  28.  
  29.   (if (or (null? left)
  30.           (null? right))
  31.       (append left right)
  32.       (do-merge left right '())))
  33.  
  34. (define (merge-sort list)
  35.   (let-values (((left right) (split-in-half list)))
  36.     (if (and (< (length left) 2)
  37.              (< (length right) 2))
  38.         (merge left right)
  39.         (merge (merge-sort left) (merge-sort right)))))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top