Given an array of size n wherein elements keep on increasing monotically upto a certain location
after which they keep on decreasing monotically, then again keep on increasing, then decreasing
again and so on. Sort the array in place (ie. using only O(1) extra memory).
Solution:
Step1: Find the point after which the decrease starts let us call it P1. O(logn)
Step2: From P1 reverse the array. O(n)
Step3: Mark the beginning of the array as P2.
Step4: Now start a inplace merge sort, where first array begins at P1 and other at P2. O(n)
