2. Natural merge sort: We can modify merge sort to take into account the order within...

Transcribed Image Text:

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 77 1| 11 | 59 | 61 | 15 | 48 | 19 The algorithm works as follows, 5 77 1 11 1 26 77 26 5 5 11 11 15 26 59 61 15 48 59 1 48 59 61 77 15 1 61 48 19 1 1 | 5 | 11 | 15 19 26 48 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? 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 77 1| 11 | 59 | 61 | 15 | 48 | 19 The algorithm works as follows, 5 77 1 11 1 26 77 26 5 5 11 11 15 26 59 61 15 48 59 1 48 59 61 77 15 1 61 48 19 1 1 | 5 | 11 | 15 19 26 48 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?

Answer rating: 100% (QA)

a Pseudocode for Natural Merge Sort function naturalMergeSortarr if ... View the full answer