Implement the following sorting algorithm. First split the given array a into nondecreasing and decreasing segments (that is, segments such that a[i] ≤ a[i + 1] ≤ ... a[i + k] or a[j] > a[j + 1] > ... > a[j + m]). Reverse all decreasing segments. Now the array is partitioned into non-decreasing segments. Merge the first two segments, then the next two, and so on, each into a non-decreasing segment. Repeat this process until all segments are merged.