Consider the following implementation of an iterative merge sort. Scan the array from its beginning and partition it into segments that are each sorted. As you find each segment, represent it as a pair of indices and place the pair at the end of an initially empty vector. Next, remove the first two pairs from the vector and merge the array segments they represent. Notice that these segments are adjacent in the array. The merge results in a larger segment that is sorted. Place the pair of indices that represents the resulting segment at the end of the vector. Repeat the steps in this paragraph until only one entry remains in the vector. Sometimes during the process, the two pairs at the beginning of the vector will represent segments that are not adjacent. In this case, move the first pair to the end of the vector and continue.
a. What is the best-case performance of this algorithm?
b. What is the worst-case performance of this algorithm?
c. Implement the algorithm.
