insertion sort and merge sort

Sorting-- insertion sort

Array(5,2,1,3,6,4)
Call 5 sorted
Shift 5 to the right, pointer now at index 2
Shift 2 and 5 both over one so 1 is at index 0, pointer now at 3
and so on and so forth
it is O(n!)

Divide and conquer algorithm
break down list of size n into n lists of 1
merge sorted lists in a manner that produces a sorted list

=====

Merge sort
Sort left half, sort right half, merge them
looks like a tree
so you end up with (1,2,5) and (3,4,6)
then we compare from A to B and decide which one gets to go into the real list