#lang racket

;;; Procedure:
;;;   merge
;;; Parameters:
;;;   sorted1, a sorted list.
;;;   sorted2, a sorted list.
;;;   may-precede?, a binary predicate that compares values.
;;; Purpose:
;;;   Merge the two lists.
;;; Produces:
;;;   sorted, a sorted list.
;;; Preconditions:
;;;   may-precede? can be applied to any two values from
;;;     sorted1 and/or sorted2.
;;;   may-precede? represents a transitive operation.
;;;   sorted1 is sorted by may-precede? That is, for each i such that
;;;     0 <= i < (length sorted1)
;;;       (may-precede? (list-ref sorted1 i) (list-ref sorted1 (+ i 1)))
;;;   sorted2 is sorted by may-precede? That is, for each i such that
;;;     0 <= j < (length sorted2)
;;;       (may-precede? (list-ref sorted2 j) (list-ref sorted2 (+ j 1)))
;;; Postconditions:
;;;   sorted is sorted by may-precede?.
;;;     For each k, 0 <= k < (length sorted)
;;;       (may-precede? (list-ref sorted k) (list-ref sorted (+ k 1)))
;;;   sorted is a permutation of (append sorted1 sorted2)
;;;   Does not affect sorted1 or sorted2.
;;;   sorted may share cons cells with sorted1 or sorted2.
(define merge
  (lambda (sorted1 sorted2 may-precede?)
    (cond
      ; If the first list is empty, return the second
      ((null? sorted1) sorted2)
      ; If the second list is empty, return the first
      ((null? sorted2) sorted1)
      ; If the first element of the first list is smaller or equal,
      ; make it the first element of the result and recurse.
      ((may-precede? (car sorted1) (car sorted2))
       (cons (car sorted1) 
             (merge (cdr sorted1) sorted2 may-precede?)))
      ; Otherwise, do something similar using the first element
      ; of the second list
      (else
       (cons (car sorted2) 
             (merge sorted1 (cdr sorted2) may-precede?))))))

;;; Names:
;;;   some-female-avengers
;;;   some-male-avengers
;;; Type:
;;;   Lists of lists of the form (identity, first, last)
;;; Summary:
;;;   Lists of avengers
(define some-female-avengers (list (list "Scarlet Witch" "Wanda" "Maximov")
                                   (list "Wasp" "Janet" "Pym")
                                   (list "Black Widow" "Natasha" "Romanoff")))
(define some-male-avengers (list (list "Hulk" "Bruce" "Banner")
                                 (list "Thor" "Donald" "Blake")
                                 (list "Quicksilver" "Pietro" "Maximov")
                                 (list "Ant Man" "Hank" "Pym")
                                 (list "Iron Man" "Tony" "Stark"))) 

;(merge some-female-avengers some-male-avengers
;      (lambda (fa ma) (string-ci<=? (car fa) (car ma))))

; (merge some-female-avengers some-male-avengers
;        (lambda (fa ma) (or (string-ci<? (caddr fa) (caddr ma))
;                            (and (string-ci=? (caddr fa) (caddr ma))
;                                 (string-ci<=? (cadr fa) (cadr ma))))))

(define stuff (vector "a" "b" "c" "d" "e" "f" "g" "h"))

(define vector-swap
  (lambda (vec i j)
    (void)))