Sort Array

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)

Median

/*********************************************
X[1...n] and Y[1....n] are 2 sorted arrays....
give O(log n) algo to find median of the array
formed by merging the 2 arrays
*********************************************/

/***
Take the middle of Arr X call it midX and middle element of
Arr Y call it midY..
***/
int findMedian(Array arrX[])
{
lowX=0
lowY=0
highX=arrX.size - 1
highY=arrY.size - 1

midX = (highX - lowX)/2
midY = (highY - lowY)/2
while(lowX != highX || lowY !=highY)
{
if(midX < midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowX=midX
highY=midY
midX = midX + (highX - lowX)/2;
midY = (highY - lowY)/2;
**/
}
else if (midX > midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowY =midY
highX=midX
midY = midY + (highY - lowY)/2;
midX = (highX - lowX)/2;
**/
}
else
{
printf("median %d",arrX[midX]);
return arrX[midX];
}
}
return arrX[midX];/*or return arrY[midY]*/
}