Given an array, write a method that would sort the array where all even elements are on the left side and all the odds are on the right.

Example Input:

{3, 6, 8, 6, 21, 44, 63, 3, 2}

Example Output:

{2, 6, 8, 6, 44, 21, 63, 3, 3}

void EvenOddSort(vector<int> &arr)
{
    if (arr.size() < 2)
        return;
 
    // Keep a left and right index
    int l = 0;
    int r = arr.size() - 1;
 
    while (l < r)
    {
        // Move left index to the right if the element is already even
        while (l < r && arr[l] % 2 == 0)
            l++;
        // Move right index to the left if the element is already odd
        while (r > l && arr[r] % 2 != 0)
            r--;
        // Otherwise swap the elements and move both indexes
        swap(arr, l++, r--);
    }
}