- First count the inversions in the left part
- Count the inversions in the right part
- Count the inversions if they are merged using modified merge procedure
- Adding the three counts gives the actual result
- Take two pointers to start of the two arrays.
- Compare the two elements to see which element goes to the sorted list first.
- Increment the corresponding index.
- Repeat the above steps until we reach the end of either of them.
- Add the remaining elements if any.
int absn = abs(n);
if( absn == 0 )
else if( absn == 1)
return (n < 0) ? (1/x) : x;
double temp = pow(x, absn/2);
result = temp*temp;
result = temp*temp*x;
return ( n < 0 )? (1/result) : result;
For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.
We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.
Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .
if( arr[low] <= arr[mid]) //left half is sorted
//If target lies in first half
if( s >= arr[low] && s < arr[mid] )
high = mid – 1;
low = mid + 1; // narrow down to right half
else // Right half is sorted
if( s > arr[mid] && s <= arr[high] )
low = mid + 1;
high = mid – 1;
Here is the iterative implementation of the above algorithm. This algorithm runs in O( log n ) time complexity.
For example the array [4, 5, 1, 2, 3] is (right) rotated twice.
Before proceeding to find a solution, let’s note some observations.
To find the number of rotations, we have to find the smallest element in the array. If we find the index of the smallest element in the array, that will indicate the number of rotations.
In the above example, the smallest number is 1 which is located at index ‘2’. We can easily verify that the array is rotated twice.
A simple approach could be to use a linear search to find the least number and return it’s index. This approach will obviously take O(n) time. Can we perform better than that?
Yes, it can be done by utilizing the sorted property of the array. Here is how we can do this.
Just like Binary search, we can use divide and conquer approach. We write a recursive function which will take the array, lower and upper bound as its parameters.
We first check whether the array is sorted from the beginning (not rotated). This can be done by checking if array[low] <= array[high]. If it is not rotated, we can simply return the index low.
Next we check if the middle element is the smallest element by comparing it with the previous and next elements.
If this condition is satisfied, then we return mid. One caution while calculating the next and previous indices is to consider the array boundaries. We have to assume that the array is circular.
//if mid is at 0, consider last element as previous
int prev = (mid – 1 + len) % len;
//if mid is the last element, consider next element as the first
int next = (mid + 1) % len;
Next, we check which portion is already sorted. If the left portion is properly sorted (without rotations), we search in the right half. Otherwise we search in the left half.
return findRotations(arr, mid+1, high);
return findRotations(arr, low, mid-1);
Even more simplified version of the algorithm is given below.
Quick sort works as follows.
A random element from the array is chosen as a pivot element. A pivot element is a special element which divides the array into left part and right part. All the elements to the left of pivot ( left part) must be less than or equal to pivot, and all the elements to the right of pivot( right part) must be greater than pivot.
At this point it is easy to understand that the pivot element is in it’s position and only left, and right parts needs to be sorted. We use recursive call to sort these parts.
Here partition process is the key to sorting.
Consider the following example to understand the partitioning process.
You can get a good understanding of the whole procedure if we look at the following animation (Image courtesy: Wikipedia).
Here is the C++ code for quick sort.This procedure runs in O(n log n) time in average case. But in the worst case, It can take up to O(n^2) time.
In this method we divide the array into two halves. We recursively sort these two parts and merge them into single array. Here the base case for recursion is just one element i.e no need to sort an array with just one element.
For example let us consider an array of 5 elements
It is divided into two sub-arrays [3,2,1] and [5,4]. We apply merge sort recursively on both the sub-arrays and merge them to become a single sorted array.
Here is how the first sub-array gets sorted.
[3,2,1] is divided into [3,2] and . No need sort the second sub-array because it just contains one element.
[3,2] is divided into , .
The merge procedure combines the arrays ,  into sorted sub-array [2,3].
Then the sub-array [2,3] is merged with  to become [1,2,3]
Finally [1,2,3] gets merged with [4,5] to become [1,2,3,4,5] which is fully sorted.
The merge procedure works as follows. The input to the merge procedure is two sorted sub-arrays.
We initialize two pointers to the first elements of two sub-arrays. We copy the lesser element among them to a temporary array and advance the corresponding pointer to the next element. We repeat this procedure until atleast one of the sub-arrays becomes empty.
Finally we copy the non-empty sub-array elements to the temporary array.
Here is the Java implementation of merge sort.
This code runs in O(n log n) time in the worst case also. But it is not an in-place sorting mechanism because we use a temporary array in the merge procedure.