Three way partitioning

Given an array of size n and a range [a, b]. The task is to partition the array around the range such that array is divided into three parts.
1) All elements smaller than a come first.
2) All elements in range a to b come next.
3) All elements greater than b appear in the end.
The individual elements of three sets can appear in any order. You are required to return the modified array.

Example 1:

Input: 
n = 5
A[] = {1, 2, 3, 3, 4}
[a, b] = [1, 2]
Output: 1
Explanation: One possible arrangement is:
{1, 2, 3, 3, 4}. If you return a valid
arrangement, output will be 1.

Example 2:

Input: 
n = 3 
A[] = {1, 2, 3}
[a, b] = [1, 3]
Output: 1
Explanation: One possible arrangement 
is: {1, 2, 3}. If you return a valid
arrangement, output will be 1.

method 1: sorting

A simple solution is to sort the array. This solution does a lot of extra rearrangements and requires O(n Log n) time.

method 2 : 

We traverse given array elements from left. We keep track of two pointers, first to store next position of smaller element (smaller than range) from beginning and second to store next position of greater element from end.

c++ implementation:

void threeWayPartition(vector<int>& array,int a, int b)
    {
        // code here 
        int l=0,r=array.size()-1;
        for(int i=0;i<=r;i++)
        {
            if(array[i]<a)
            {
                swap(array[i],array[l]);
                l++;
            }
            else if(array[i]>b)
            {
                swap(array[i],array[r]);
                r--;
                i--;
            }
        }
    }

Time Complexity: O(n) 

space Complexity: O(1)