Quicksort using first element pivot 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 &lt;vector&gt;

using namespace std;
using uint = unsigned int;

uint PartitionSub(vector&lt;uint&gt;&amp; inp, uint l, uint r, uint&amp; numOfCmp);

void QuickSort(vector&lt;uint&gt;&amp; inp, uint l, uint r, uint&amp; numOfCmp)
{
    if (r - l &lt; 2)
        return;

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

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

uint PartitionSub(vector&lt;uint&gt;&amp; inp, uint l, uint r, uint&amp; numOfCmp)
{
    auto swap = [&amp;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 &lt;= r; j++)
    {
        ++numOfCmp;
        if (inp[j] &lt;= p)
        {
            if (i != j)
                swap(i, j);
            i++;
        }
    }

    uint newPivotIdx = i - 1;
    swap(l, newPivotIdx);
    return newPivotIdx;
}
Prefer standard integer types

Instead of: 

using uint = unsigned int;


Prefer

#include &lt;cstdint&gt;
//use the std::uint32_t in code (or whichever width)


Don't use namespace std

Common advice which will help guard against namespace collisions. In your case I think you could get away with just:

using std::vector;


Quicksort Algorithm

A common optimization to remove average case comparisons is to more intelligently select your pivot. One approach which strengthens the asymptotic runtime of the algorithm is the 'median of fives' approach. In this approach you select your pivot to be the median of 'the median of each of the n/5 sublists of length 5'. In practise, however, this could increase the number of comparisons. It's hard to recommend a strategy without knowing the size and characteristics of your input.