#lang racket
(require racklog)

(define %rev
  (%rel (x xs ys acc)
        [(null acc acc)]
        [(xs ys)
         (%rev xs ys null)]
        [((cons x xs) ys acc)
         (%rev xs ys (cons x acc))]))

(define %my-app
  (%rel (x xs ys zs)
        [(null ys ys)]
        [((cons x xs) ys (cons x zs))
         (%my-app xs ys zs)]))

(define %merge
  (%rel (x xs y ys zs zst)
        [(null ys ys)]
        [(xs null xs)]
        [((cons x xs) (cons y ys) (cons y zs))
         (%> x y)
         (%merge (cons x xs) ys zs)]
        [((cons x xs) (cons y ys) (cons x zs))
         (%<= x y)
         (%merge xs (cons y ys) zs)]))

(define %len
  (%rel (x xs n m)
        [(null 0)]
        [((cons x xs) m)
         (%len xs n)
         (%is m (+ n 1))]))

(define %split
  (%rel (x xs ys zs acc m n tmp)
        [(xs ys zs)
         (%len xs n)
         (%is m (/ n 2))
         (%split xs ys zs null m)]
        [((cons x xs) ys zs acc n)
         (%len acc m)
         (%< m n)
         (%my-app acc (cons x null) tmp)
         (%split xs ys zs tmp n)]
        [(xs acc xs acc n)
         (%len acc m)
         (%>= m n)]))

(define %mergesort
  (%rel (xs ys n s1 s2 ms1 ms2)
        [(xs xs)
         (%len xs n)
         (%<= n 1)]
        [(xs ys)
         (%len xs n)
         (%> n 1)
         (%split xs s1 s2)
         (%mergesort s1 ms1)
         (%mergesort s2 ms2)
         (%merge ms1 ms2 ys)]))

(define (merge xs ys)
  (cond
    [(null? xs) ys]
    [(null? ys) xs]
    [(< (car xs) (car ys)) (cons (car xs) (merge (cdr xs) ys))]
    [else (cons (car ys) (merge xs (cdr ys)))]))

(define (split xs)
  (define (iter xs acc n)
    (if (< (length acc) n)
        (iter (cdr xs) (append acc (list (car xs))) n)
        (cons acc xs)))
  (iter xs null (/ (length xs) 2)))

(define (mergesort xs)
  (if (= (length xs) 1)
      xs
      (merge (mergesort (car (split xs)))
             (mergesort (cdr (split xs))))))