- Show that the running time of the merge-sort algorithm on an n-element sequence is O(nlogn), even when n is not a power of two.
- An algorithm that sorts key-value entries by key is said to be straggling if any time two entries ei and ej have equal keys, and ei appears before ej in the input, then the algorithm places ei after ej in the output. Describe a change to the merge-sort algorithm to make it straggling.
- Of the n! possible inputs to a given comparison-based sorting algorithm on a list of n elements, what is the absolute maximum number of inputs that could be correctly sorted with just n comparisons? Prove your answer.
- Suppose you are throwing a fancy dinner party with n guests total. When a guest walks through the front door, they check their coat in and continue to the party. However, the coat check mixes up all of the coats during dinner, so that afterward each guest receives a random coat when they prepare to leave. In other words, each guest gets their own coat with probability 1/n. What is the expected number of guests who get their correct coat?
- Suppose we are given two n-element sorted sequences, A and B. Each of these sequences have distinct elements, but there might be repeated elements between the sequences. Write the pseudocode for an O(n) time function that takes A and B as arguments and returns a new sorted sequence which is the intersection of A and B.