Choose the sorting algorithm that would be the best for each scenario in order to reduce the expected running time.
(a) You are running a library catalog. You know that the books in your collection are almost in sorted ascending order by title, with the exception of one book which is in the wrong place. You want the catalog to be completely sorted in ascending order.
(b) You are working on an embedded device (an ATM) that only has 4KB of free memory, and you wish to sort the 2,000,000 transactions withdrawal history by the amount of money withdrawn (discarding the original order of transactions).
(c) To determine which of your Facebook friends were early adopters, you decide to sort them by their Facebook account ids, which are 64-bit integers. (Recall that you are super popular, so you have very many Facebook friends.)
1. Insertion Sort
2. Merge Sort
3. Heap Sort
4. Counting Sort