The same SO question was originally posted here in Python. Following the advice of @user24714692, I coded everything in CPP and created a new question.

I’ve implemented a version of radix sort (the version that allows sorting integers whose values go up to n² where n is the size of the list to sort) in C++ for benchmarking against the standard built in sort (a 3-part hybrid sorting algorithm).

Surprisingly, my radix sort implementation, even without using a hashmap (using a direct access array instead), is slower than the standard sort even for larger input sizes. Since I’m O(n) and the built-in is O(nlogn) there should be ways to micro optimise my coded. I’m seeking advice on optimizing my implementation to achieve better performance. I’m not doing this for practical purposes but just for learning purposes as I’m fairly new to programming, therefore I’m not looking for external libraries to magically improve my code without understand why it makes it better.

Are there micro-optimisations I could bring? Is my code really O(n)?

Time is expressed in seconds:

Size            Radix Sort No Hashmap           std::sort
1.000e+03               2.981e-04               1.059e-04
1.000e+04               2.612e-03               1.330e-03
1.000e+05               3.157e-02               1.608e-02
2.000e+05               5.678e-02               3.460e-02
1.000e+06               3.820e-01               1.951e-01
2.000e+06               8.998e-01               4.029e-01
3.000e+06               1.365e+00               6.243e-01
4.000e+06               1.981e+00               8.314e-01
5.000e+06               2.607e+00               1.078e+00
6.000e+06               3.024e+00               1.317e+00
1.000e+07               5.679e+00               2.224e+00

Code used:

#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <iomanip>

void radix_sort_no_hashmap(std::vector<long long>& arr, long long size) {
    std::vector<std::vector<long long>> least_sig_digit(size);
    for (long long num : arr) {
        long long q = num / size;
        long long r = num % size;
        least_sig_digit[r].push_back(q);
    }
    std::vector<std::vector<long long>> highest_sig_digit(size);
    for (long long k = 0; k < size; ++k) {
        for (long long q : least_sig_digit[k]) {
            highest_sig_digit[q].push_back(q * size + k);
        }
    }
    long long i = 0;
    for (long long k = 0; k < size; ++k) {
        for (long long num : highest_sig_digit[k]) {
            arr[i++] = num;
        }
    }
}

void benchmark_sorting_algorithms(std::vector<long long>& sizes, std::vector<double>& radix_times, std::vector<double>& std_sort_times) {
    for (long long size : sizes) {
        std::vector<long long> array(size);

        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<long long> dis(0, size-1);

        for (long long& num : array) {
            num = dis(gen);
            num = num * num; // To ensure large values
        }

        auto new_arr1 = array;
        auto start = std::chrono::high_resolution_clock::now();
        radix_sort_no_hashmap(new_arr1, size);
        auto end = std::chrono::high_resolution_clock::now();
        radix_times.push_back(std::chrono::duration<double>(end - start).count());

        auto new_arr2 = array;
        start = std::chrono::high_resolution_clock::now();
        std::sort(new_arr2.begin(), new_arr2.end());
        end = std::chrono::high_resolution_clock::now();
        std_sort_times.push_back(std::chrono::duration<double>(end - start).count());

        // Make sure that the arrays are sorted correctly
        for (long long i = 0; i < size; ++i) {
            if (new_arr1[i] != new_arr2[i]) {
                std::cout << "Sorting failedn";
                return;
            }
        }
    }
}

int main() {
    std::vector<long long> sizes = {1000, 10000, 100000, 200000, 1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 10000000};
    std::vector<double> radix_times;
    std::vector<double> std_sort_times;

    benchmark_sorting_algorithms(sizes, radix_times, std_sort_times);

    std::cout << "SizettRadix Sort No Hashmapttstd::sortn";
    for (long long i = 0; i < sizes.size(); ++i) {
        std::cout << std::scientific << std::setprecision(3) << (float)sizes[i] << "tt" << radix_times[i] << "tt" << std_sort_times[i] << "n";
    }
    return 0;
}