Не используйте qsort

Используйте std::sort (с функтором или лямбда-функцией) вместо функции qsort стандартной библиотеки C.

Во-первых, std::sort обычно реализована как гибридный алгоритм Introsort (Introspective Sort), который комбинирует сильные стороны быстрой сортировки, пирамидальной сортировки и сортировки вставками, чтобы обеспечить высокую производительность в среднем и гарантированно избежать квадратичной сложности в худшем случае.

Во-вторых, функция qsort использует указатель на функцию компаратора, а значит обязана вызывать её при сортировке, тогда как шаблонная функция std::sort может инлайнить компаратор (функцию, функтор, лямбда-функцию). В результате std::sort отрабатывает значительно быстрее (см. ниже результаты).

Пример:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <chrono>
#include <algorithm>
#include <functional>

// Компаратор как обычная функция
bool compare_func(int a, int b) {
    return a < b;
}

// Компаратор как функтор
struct CompareFunctor {
    bool operator()(int a, int b) const {
        return a < b;
    }
};

// Компаратор для qsort (C-стиль)
int compare_qsort(const void* a, const void* b) {
    return *(const int*)a - *(const int*)b;
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr << "Usage: " << argv[0] << " <array_size>" << std::endl;
        return 1;
    }

    int size = std::atoi(argv[1]);
    if (size <= 0) {
        std::cerr << "Array size must be positive" << std::endl;
        return 1;
    }

    std::srand(static_cast<unsigned>(std::time(nullptr)));

    // Выделяем память под массивы для каждого теста
    int* arr_qsort = new int[size];
    int* arr_func = new int[size];
    int* arr_functor = new int[size];
    int* arr_lambda = new int[size];
    int* arr_std_func = new int[size];

    // Заполняем все массивы одинаковыми данными
    for (int i = 0; i < size; i++) {
        int value = std::rand();
        arr_qsort[i] = value;
        arr_func[i] = value;
        arr_functor[i] = value;
        arr_lambda[i] = value;
        arr_std_func[i] = value;
    }

    // === 1. qsort с указателем на функцию (C-style) ===
    auto start = std::chrono::high_resolution_clock::now();
    qsort(arr_qsort, size, sizeof(int), compare_qsort);
    auto end = std::chrono::high_resolution_clock::now();
    auto time_qsort = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    // === 2. std::sort с указателем на функцию ===
    start = std::chrono::high_resolution_clock::now();
    std::sort(arr_func, arr_func + size, compare_func);
    end = std::chrono::high_resolution_clock::now();
    auto time_func = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    // === 3. std::sort с функтором ===
    start = std::chrono::high_resolution_clock::now();
    std::sort(arr_functor, arr_functor + size, CompareFunctor());
    end = std::chrono::high_resolution_clock::now();
    auto time_functor = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    // === 4. std::sort с лямбдой ===
    start = std::chrono::high_resolution_clock::now();
    std::sort(arr_lambda, arr_lambda + size, [](int a, int b) { return a < b; });
    end = std::chrono::high_resolution_clock::now();
    auto time_lambda = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    // === 5. std::sort с std::function ===
    std::function<bool(int, int)> comp = [](int a, int b) { return a < b; };
    start = std::chrono::high_resolution_clock::now();
    std::sort(arr_std_func, arr_std_func + size, comp);
    end = std::chrono::high_resolution_clock::now();
    auto time_std_func = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    // Вывод результатов
    std::cout << "Array size: " << size << std::endl;
    std::cout << "========================================" << std::endl;
    std::cout << "qsort (C function pointer):   " << time_qsort << " ms" << std::endl;
    std::cout << "std::sort (function pointer): " << time_func << " ms" << std::endl;
    std::cout << "std::sort (functor):          " << time_functor << " ms" << std::endl;
    std::cout << "std::sort (lambda):           " << time_lambda << " ms" << std::endl;
    std::cout << "std::sort (std::function):    " << time_std_func << " ms" << std::endl;
    std::cout << "========================================" << std::endl;

    // Очистка памяти
    delete[] arr_qsort;
    delete[] arr_func;
    delete[] arr_functor;
    delete[] arr_lambda;
    delete[] arr_std_func;

    return 0;
}

Вывод:

// Windows, MSVC2022
Array size: 10000000
========================================
qsort (C function pointer):   716 ms
std::sort (function pointer): 651 ms
std::sort (functor):          488 ms
std::sort (lambda):           499 ms
std::sort (std::function):    760 ms
========================================
// Linux (WSL2), g++11.4
Array size: 10000000
========================================
qsort (C function pointer):   1050 ms
std::sort (function pointer): 804 ms
std::sort (functor):          625 ms
std::sort (lambda):           584 ms
std::sort (std::function):    1002 ms
========================================

При использовании std::function в качестве компаратора, производительность std::sort ухудшается и даже превышает qsort.

std::function - это обёртка, которая может хранить любой вызываемый объект (функцию, лямбду, функтор) и для этого использует технику, называемую type erasure.

Очень упрощенно std::function устроен внутри следующим образом:

template<typename Signature>
class function {
    // Внутренний интерфейс
    struct callable_base {
        virtual ~callable_base() {}
        virtual bool invoke(int a, int b) const = 0;
    };

    template<typename F>
    struct callable_impl : callable_base {
        F f;
        callable_impl(F f) : f(std::move(f)) {}
        bool invoke(int a, int b) const override {
            return f(a, b);  // виртуальный вызов!
        }
    };

    callable_base* ptr;  // указатель на базовый класс
};

Что происходит при сортировке:

Виртуальный вызов: Каждое сравнение comp(a, b) превращается в ptr->invoke(a, b) → это виртуальный вызов через указатель на vtable
Нет инлайнинга: Компилятор не может заинлайнить компаратор, потому что реальный тип скрыт за интерфейсом
Дополнительная косвенность: Два уровня косвенности (указатель на объект + виртуальная функция)

Вывод: Не используйте std::function в качестве компаратора std::sort.