#lang scheme
(provide (all-defined-out))
;; Don't change the lines above unless you know what you're doing!
;; The functions below can be short; none of mine is longer than 8 lines.
;; -- Dana

;; list-head : list number -> list
;; Returns a list of the first pos elements of lst, in the same order.
;; You may assume the number is a non-negative integer no greater than
;; the length of the list. For bonus points, throw appropriate exceptions!
(define (list-head lst pos) 'not-implemented)

;; split-position : list -> number
;; Returns the position immediately before the midpoint in the list.
(define (split-position lst) 'not-implemented)

;; first-half : list -> list
;; Returns the first half of the list, as nearly as possible.
;; When the list is odd in length, the first half is the shorter.
(define (first-half lst) 'not-implemented)

;; second-half : list -> list
;; Returns the second half of the list, as nearly as possible.
;; When the list is odd in length, the second half is the longer.
(define (second-half lst) 'not-implemented)

;; merge : predicate list list -> list
;; Given a predicate p and 2 lists sorted according to p,
;; merges the lists into a single list sorted according to p.
(define (merge p left right) 'not-implemented)

;; merge-sort : predicate list -> list
;; Given a predicate p and a list lst,
;; returns a list of the elements of lst sorted according to p.
(define (merge-sort p lst) 'not-implemented)

;; sort-numbers-decreasing : list-of-nums -> list-of-nums
;; Given a list of numbers, returns a list of those numbers in decreasing order.
;; (OK, non-increasing order technically, but the name is long enough already!)
;; (Hint: This is very simple using curry and merge-sort!)
(define sort-numbers-decreasing 'not-implemented)

;; sort-strings-increasing : list-of-strings -> list-of-strings
;; Given a list of strings, returns a list of those strings in increasing order.
(define sort-strings-increasing 'not-implemented)

;; The approach to implementing merge-sort suggested by the sequence above
;; has run-time complexity in O(n lg n), but the linear factor is somewhat
;; larger than it could be. For bonus points, explain why in comments and give
;; a more efficient implementation.