Problem
1. Give an example input list that requires merge-sort and heapsort to take O(nlogn) time to sort, but insertion-sort runs in O(n) time. What if you reverse this list?
2. Describe, in pseudo-code, how to perform path compression on a path of length h in O(h) time in a tree-based partition union/find structure.