Develop a sort routine that uses the following 
  building blocks: 

  (a) merge (this is mergeSorted as described)
  (b) longest (this extracts the longest sorted prefix
  (c) rest (this gives you what remains after you extract that)


longest([1, 3, 4, 7, 2, 4, 1]) is [1, 3, 4, 7] 
rest([1, 3, 4, 7, 2, 4, 1]) is [2, 4, 1]
merge([1, 3, 5], [2, 4]) is [1, 2, 3, 4, 5]

sort = ?

define sort(seq) 
  if empty seq
    return seq 
  else 
    return merge(longest(seq), sort(rest(seq)))

// sequence: [1, 3, 2, 4, 5, 1, 9, 7]
//            ----
// prefix: I see 8 (possibly nine)
// longest sorted (ascending) prefix: [1, 3]
// [1, 3, 5, 7, 2, 4, 6, 8] 
// ------------
// let's implement Sequence
import java.util.ArrayList; 

public class Sequence {
  private ArrayList<Integer> values; 
  public Sequence() {
    this.values = new ArrayList<Integer>();
  }
  public int size() {
    return this.values.size();  
  }
  public String toString() {
    return this.values + "";  
  }
  public void add(int n) {
    this.values.add( n );  
  }
  // merges two sorted sequences (this and other) (a) 
  // or the longest sorted prefixes (b) 
  // mergeSorted([1, 3, 5, 2, 4], [4, 5, 3, 7]) will produce
  // mergeSorted([1, 3, 5], [4, 5]) which will produce [1, 3, 4, 5, 5] 
  public Sequence mergeSorted(Sequence other) {
     return null;
  }
}