Quicksort + Modified Insertion sort verses Quicksort + Standard Insertion Sort

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

// Quicksort + Modified Insertion sort verses Quicksort + Standard Insertion Sort
// Switches to Insertion sort <= 32 elements
// Contact Email [email protected]
// Created by I.A

// Cache Clearing
// 32MB
const size_t CACHE_SIZE_BYTES = 32 * 1024 * 1024;
const size_t CACHE_SIZE_INTS = CACHE_SIZE_BYTES / sizeof(int);
std::vector<int> cache_trasher(CACHE_SIZE_INTS, 0);

void flushCache() {
    // Use volatile to prevent the compiler from optimizing this loop away
    volatile int* p = cache_trasher.data();

    // Step by 16 integers (64 bytes) to touch every standard CPU cache line
    for (size_t i = 0; i < CACHE_SIZE_INTS; i += 16) {
        p[i] += 1;
    }
}

void standardInsertionSortSlice(std::vector<int>& arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void customJumpSortSlice(std::vector<int>& arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            if (j >= low + 1) {
                arr[j + 1] = arr[j];
                if (arr[j - 1] > key) {
                    arr[j] = arr[j - 1];
                    j -= 2;
                } else {
                    arr[j] = key;
                    goto placed;
                }
            } else {
                arr[j + 1] = arr[j];
                j--;
            }
        }
        arr[j + 1] = key;
        placed:;
    }
}

int medianOfThree(std::vector<int>& arr, int low, int high) {
    int mid = low + (high - low) / 2;
    if (arr[mid] < arr[low])
        std::swap(arr[low], arr[mid]);
    if (arr[high] < arr[low])
        std::swap(arr[low], arr[high]);
    if (arr[mid] < arr[high])
        std::swap(arr[mid], arr[high]);
    return arr[high];
}

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = medianOfThree(arr, low, high);
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

// ---------------------------------------------------------
// Hybrid QuickSort Algorithms (Cutoff threshold: 32 elements)
// ---------------------------------------------------------

void quickSortStandardInsertion(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // Switch to insertion sort for subarrays with 32 or fewer elements
        if (high - low + 1 <= 32) {
            standardInsertionSortSlice(arr, low, high);
            return;
        }

        int pi = partition(arr, low, high);

        quickSortStandardInsertion(arr, low, pi - 1);
        quickSortStandardInsertion(arr, pi + 1, high);
    }
}

void quickSortCustomJump(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        // Switch to custom jump sort for subarrays with 32 or fewer elements
        if (high - low + 1 <= 32) {
            customJumpSortSlice(arr, low, high);
            return;
        }

        int pi = partition(arr, low, high);

        quickSortCustomJump(arr, low, pi - 1);
        quickSortCustomJump(arr, pi + 1, high);
    }
}

// ---------------------------------------------------------
// Main Benchmark
// ---------------------------------------------------------

int main() {
    const int NUM_ELEMENTS = 10000; // Increased array size to showcase QuickSort behavior
    const int NUM_TRIALS = 10000;      // Adjusted trial count for balanced execution time

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dist(1, 100000);

    double totalQuickStd = 0, totalQuickJump = 0;

    for (int t = 0; t < NUM_TRIALS; ++t) {
        std::vector<int> data1(NUM_ELEMENTS);
        for (int& x : data1) x = dist(gen);
        std::vector<int> data2 = data1;

        // Benchmark QuickSort with Standard Insertion
        //flushCache();
        auto s1 = std::chrono::steady_clock::now();
        quickSortStandardInsertion(data1, 0, NUM_ELEMENTS - 1);
        auto e1 = std::chrono::steady_clock::now();
        totalQuickStd += std::chrono::duration<double>(e1 - s1).count();

        // Benchmark QuickSort with Custom Jump Sort
        //flushCache();
        auto s2 = std::chrono::steady_clock::now();
        quickSortCustomJump(data2, 0, NUM_ELEMENTS - 1);
        auto e2 = std::chrono::steady_clock::now();
        totalQuickJump += std::chrono::duration<double>(e2 - s2).count();

        // Verify Logic
        if (!std::is_sorted(data1.begin(), data1.end()) || !std::is_sorted(data2.begin(), data2.end())) {
            std::cout << "CRITICAL ERROR: Array sorting failed!" << std::endl;
            return 1;
        }
    }

    std::cout << std::left << std::setw(30) << "Algorithm" << " | " << "Total Time (s)" << std::endl;
    std::cout << "--------------------------------------------------------" << std::endl;
    std::cout << std::setw(30) << "QuickSort + Standard Insertion" << " | " << std::fixed << std::setprecision(6) << totalQuickStd << std::endl;
    std::cout << std::setw(30) << "QuickSort + Custom Jump" << " | " << std::fixed << std::setprecision(6) << totalQuickJump << std::endl;

    return 0;
}