mergesort() merges the subarrays of an array that is already in order. Another top-down version of mergesort alleviates this problem by merging only runs, subarrays with ordered elements. Merging is...

mergesort() merges the subarrays of an array that is already in order. Another top-down version of mergesort alleviates this problem by merging only runs, subarrays with ordered elements. Merging is applied only after two runs are determined. For example, in the array [6 7 8 3 4 10 11 12 13 2], runs [6 7 8] and [3 4] are first merged to become [3 4 6 7 8], then runs [10 11 12 13] and [2] are merged to become [2 10 11 12 13], and finally, runs [3 4 6 7 8] and [2 10 11 12 13] are merged to become [2 3 4 6 7 8 10 11 12 13]. Implement this algorithm and investigate its complexity. A mergesort that takes advantage of a partial ordering of data (that is, uses the runs) is called a natural sort. A version that disregards the runs by always dividing arrays into (almost) even sections is referred to as straight merging.