3. (20 points) True or False. If False, show the reason (a) No comparison sort can do better than e(n log n). (b) On a sequence that is nearly sorted, the Insertion Sort is faster than the Merge Sort. (c) On a sequence that is nearly sorted, the Merge Sort is faster than the Quick Sort. (d) On a sequence that is nearly sorted in reverse order, the Insertion Sort runs faster than the Merge Sort. (e) On a sequence that is nearly sorted in reverse order, the Heap Sort (with max Heap) runs faster (f) If the length of a sequence is doubled, the Selection Sort will take about twice as long to run. (g) The Selection Sort will take the same time to run on a sequence of length n, regardless of the (h) The Insertion Sort will take the same time to run on a sequence of length n, regardless of the (i) The Quick Sort will take the same time to run on a sequence of length n, regardless of the than the Merge Sort. original order of the elements. original order of the elements. original order of the elements. order of the elements 0) The Heap Sort will take the same time to run on a sequence of length n, regardless of the original