Define a sorting algorithm to be parsimonious if it never compares the same pair of input values twice. (Assume that all the values being sorted are distinct.) For example, it was shown in the notes that quicksort is parsimonious.

A) Is insertion sort parsimonious? Justify your answer with either a counterexample or a brief argument.

B) Is merge sort parsimonious? Justify your answer with either a counterexample or a brief argument.

C) Is heap sort parsimonious? Justify your answer with either a counterexample or a brief argument.