I'm trying to get my Quicksort implementation doing fewer comparisons. The first element is used as a pivot. Could you give me some directions if there are any places that should be optimized in a sense of making fewer comparisons? As I understand, it's due to a redundant recursion pass, since the partition subroutine and comparisons counting in it are implemented correctly.

#include <vector>

using namespace std;
using uint = unsigned int;

uint PartitionSub(vector<uint>& inp, uint l, uint r, uint& numOfCmp);

void QuickSort(vector<uint>& inp, uint l, uint r, uint& numOfCmp)
{
    if (r - l < 2)
        return;

    uint newPivotIdx = PartitionSub(inp, l, r, numOfCmp);

    QuickSort(inp, l, newPivotIdx, numOfCmp);
    QuickSort(inp, newPivotIdx + 1, r, numOfCmp);
}

uint PartitionSub(vector<uint>& inp, uint l, uint r, uint& numOfCmp)
{
    auto swap = [&inp](uint a, uint b)
    {
        uint buf = inp[a];
        inp[a] = inp[b];
        inp[b] = buf;
    };

    //numOfCmp += r - l; // we can use this, but ++numOfCmp just before     
                         // comparison is more clear
    uint i = l + 1;
    uint j = l + 1;

    uint p = inp[l];

    for (; j <= r; j++)
    {
        ++numOfCmp;
        if (inp[j] <= p)
        {
            if (i != j)
                swap(i, j);
            i++;
        }
    }

    uint newPivotIdx = i - 1;
    swap(l, newPivotIdx);
    return newPivotIdx;
}