Sorts

insert sort		O(n^2)		in-place
	first i elements are sorted each time through the loop for i=1..n

selection sort		O(n^2)		in-place
	first i elements are the smallest elements each time through the loop for i=0..n

quick-sort		avg O(n log n) worst O(n^2)	in-place
	divide and conquer - pick random element, split input into <, =, and > element (pivot)
	recurse on < and > sets

merge-sort		O(n log n)	uses extra memory
	split array into two halves, sort each half (recursively using merge-sort)
	merge 2 resultant sorted arrays

heap-sort		O(n log n)	in-place
	build an array based heap, move top element to end of array using rightmost child as top
	reheapify, move new top element to end-1, repeat

bucket-sort		O(n)		uses extra memory
	good when there are only a fixed (small) number of distinct keys
	create a bucket for each key, scan elements moving each element into appropriate bucket

radix-sort		O(kn)	(k is size of key)	uses extra-memory
	do a bucket sort on one digit (letter) of the key at a time, requires k passes
	can be done with the most significant (msf) or least significant digit first (lsf)
	lsf is the common approach

Amortization

cost of TreePtrArray::setElement

Want to average cost over a number of calls

How to compute average (ask)

	total time/number of calls

assume no replacements, so num of calls = N (number of elements in array)

What is total cost just before a doubling (say N=128)

	TC(n) = TC(n/2)	+  	 1   +    n/2     			+     n/2
		cost to n/2	cost to double from n/2 to n		number of addl inserts
				alloc + copies

	TC(n) = n+1+TC(n/2) =
		n + 1 + n/2 + 1 + n/4 + 1 + n/8 + 1 + ... =
		log n + n(1 + 1/2 + 1/4 + 1/8 + ... ) =
		log n + 2n

	theta(n) is total cost	
		divide by n inserts

	theta(1) for each insert