Корректировка сортировки вектора целых по вектору векторов

Недавно я попытался реализовать радикальную сортировку для вектора пары целых чисел (где второй элемент рассматривается только тогда, когда первые элементы равны). Я сделал это, применив сортировку отсчета дважды — сначала ко второму элементу пары, а затем к первому элементу. Вот как я сначала реализовал сортировку отсчетов:

//vector to be sorted (of size n).
vector<int> arr;

//arr gets filled here//N-1 is the maximum number which can occur in the array. N was equal to n in my case
vector<vector<int> > mat(N);

for (int i=0;i<n;i++)
{
mat[arr[i]].push_back(i);
}

//array in which the sorted array will be stored
vector<int> arr2;

for (int i=0;i<N;i++)
{
for(int j=0;j<sz(mat[i]);j++) arr2.push_back(arr1[mat[i][j]]);
}

Первый цикл for явно выполняется в O (n). Поскольку массив ‘mat’ содержит ровно n записей, он будет доступен не более 2n раз во втором (вложенном) цикле. Это подразумевает, что вышеприведенный код имеет временную сложность O (n), как и должно быть.

Затем я сравнил время выполнения этого кода с STL sort () (который имеет временную сложность O (nlog (n))), запустив оба из них в массиве из 10 ^ 6 элементов. К моему большому удивлению, STL sort () в итоге работал немного лучше, чем моя реализация сортировки по основанию.

Затем я изменил свою реализацию сортировки подсчета на следующее:

//vector to be sorted (of size n).
vector<int> arr;

//arr gets filled here

//N-1 is the maximum number which can occur in the array. N was equal to n in my case
vector<int> temp(N,0);

for(int i=0;i<n;i++) temp[arr[i]]++;

for(int i=1;i<N;i++) temp[i]+=temp[i-1];

//array in which the sorted array will be stored
vector<int> arr2(n);

for(int i=n-1;i>=0;i--) arr2[--temp[arr[i]]]=arr[i];

На этот раз радикальная сортировка работала примерно в 5-6 раз быстрее, чем сортировка STL (). Это наблюдение заставляет меня задуматься, почему моя первая реализация сортировки по основанию работает намного медленнее, чем вторая, когда оба они являются O (n)?