2. Natural merge sort: We can modify merge sort to take into account the order within the input list. In this algorithm we

make an initial pass over the input list to determine the sequences of numbers that are in order. The algorithm then

merges these ordered sublists. For example, given the array

A= 26 5 771 | 11 | 59 | 61

15 48 19

The algorithm works as follows,

26

5

1

26 77

5

111 59 61 15 48

1

1

48 59 61

15

1

11 15 26 48 59 61 77

5 11 15 19 26 48

19

1

59 61 77

19

19

a) write pseudocode for this algorithm.

b) What is the best case for this algorithm and what is its time complexity?

c) What is the worst case for this algorithm and what is its time complexity?