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
public void add(T datum);  
// 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>();
// d.add(5.5);
// d.add(2.0);
// d.add(3.0);    
// d.add(6.1);
// d.add(2,9.0);   // put 9.0 into position 2
//
// d currently contains {5.5, 2.0, 9.0, 3.0, 6.1}
//
// System.out.print(d.remove(1)); // prints 2.0 and deletes
// System.out.print(d.get(1));    // prints 9.0
// d.set(1,4.0);    // replace element at pos 1 with 4.0
// System.out.print(d.get(1)*d.get(2)); // prints 12.0

Other things the teacher recommends you review

• Take an array of ints, heapify them, and then sort them.
• Revisit the solution to the median problem
• The various sorting routines: bubbleSort, insertionSort, selectionSort, heapSort, quickSort, and mergeSort