## Mergesort using Scheme

```;; Mergesort in Scheme (examples at bottom of page)

;; Apply f n times to a datum
(define (repeated f n) (lambda (datum)
(cond ((= n 0) datum)
(else (f ((repeated f (- n 1)) datum))))))

;; Return left half of list
;; If list contains odd number of elements, put the
;;   middle element in the right half (example at bottom)
(define (left l)
(left-helper l (ceiling (/ (length l) 2))))
(define (left-helper l n)
(cond ((= n 0) ())
(else (cons (car l)
(left-helper (cdr l) (- n 1))))))

;; Return right half of list
;; If list contains odd number of elements, this half
;;   will contain one more element than the left half
(define (right l)
((repeated cdr (ceiling (/ (length l) 2))) l))

;; Given two lists that are in ascending order, merge them
;;   into one list that is in ascending order
(define (merge l1 l2)
(cond ((null? l1) l2)
((null? l2) l1)
((< (car l1) (car l2))
(cons (car l1) (merge (cdr l1) l2)))
(else
(cons (car l2) (merge l1 (cdr l2))))))

;; Take a list of numbers and sort it into ascending order
(define (mergesort l)
(cond ((< (length l) 2) l)
(else (merge (mergesort (left l))
(mergesort (right l))))))

; Examples:
; > (define a '(1 2 3 4 5)
; > (left a)
; (1 2 3)
; > (right a)
; (4 5)
; > (merge '(1 3 4) '(2 5 6 7))
; (1 2 3 4 5 6 7)
; > (define b '(4 2 7 4 3 5 1 7 7 6 3))
; > (mergesort b)
; (1 2 3 3 4 4 5 6 7 7 7)
```

## Some useful things about ArrayList<Comparable>

```The ArrayList abstraction

// Note that indexing starts at 0

// Insert datum at end of ArrayList
// Insert datum at position pos in ArrayList
public void add(int pos, T datum);

// Number of elements in ArrayList
public int size();

// Sets reference at position index to element
public void set(int index, T element);

// Returns element at position index
public T get(int index);

// Returns element at position index, then deletes it
public T remove(int index);

// Examples:
//
// ArrayList<Double> d = new ArrayList<Double>();