Partition the list into three parts

Given a pivot x, and a list lst, partition the list into three parts.

1.The first part contains all elements in lst that are less than x

2.The second part contains all elements in lst that are equal to x

3. The third part contains all elements in lst that are larger than x

Ordering within a part can be arbitrary.

For example, given x = 10 and lst = [9, 12, 3, 5, 14, 10, 10], one partition maybe [9, 3, 5, 10, 10, 12, 14].

Example:

Input:  x = 10, lst = [9, 12, 3, 5, 14, 10, 10]
Output: [9, 3, 5, 10, 10, 14, 12]

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> partition(vector<int> &arr, int pivot)
{
    int i, temp, top = arr.size() - 1, mid = 0;
    bool step = true;
    for (i = 0; i <= top - mid; i++)
    {
        if (mid && step)
        {
            arr[i] = arr[i + mid];
        }
        step = true;
        if (arr[i] > pivot)
        {
            if (arr[top] == pivot)
            {
                arr[top--] = arr[i];
                arr[i] = arr[i + (++mid)];
            }
            else
            {
                temp = arr[i];
                arr[i] = arr[top];
                arr[top--] = temp;
                step = false;
            }
            i--;
        }
        else if (arr[i] == pivot)
        {
            mid++;
            i--;
        }
    }
    while (mid--)
    {
        arr[i++] = pivot;
    }
    return arr;
}
int main()
{
    int x = 10;
    vector<int> arr = {9, 12, 3, 5, 14, 10, 10};

    vector<int> res = partition(arr, x);

    cout << "[";

    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i];
        if (i != res.size() - 1)
            cout << ", ";
    }
    cout << "]";

    return 0;
}