Suppose that we are comparing implementations of BubbleSort and MergeSort on the same machine.

For an input of size n, BubbleSort runs in 5n2 steps, while MergeSort runs in 100n log2 n steps.

a) For which values of n does BubbleSort beat MergeSort? Show your reasoning.

b) Write pseudocode for a better algorithm that takes advantage of both BubbleSort and MergeSort on any input size n.