std::sort versus Quicksort + Modified Insertion sort verses Quicksort + Standard Insertion Sort

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

// std::sort versus Quicksort + Modified Insertion sort verses Quicksort + Standard Insertion Sort
// Tests RANDOM, REVERSE_SORTED, NEARLY_SORTED_ASC, NEARLY_SORTED_DESC, MANY_DUPLICATES, and ORGAN_PIPE
// Switches to Insertion sort <= 32 elements
// Contact Email [email protected]
// Created by I.A

// Cache Clearing
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() {
    volatile int* p = cache_trasher.data();
    for (size_t i = 0; i < CACHE_SIZE_INTS; i += 16) {
        p[i] += 1;
    }
}

// ---------------------------------------------------------
// Insertion Sorts
// ---------------------------------------------------------

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:;
    }
}

// ---------------------------------------------------------
// Quicksort Core
// ---------------------------------------------------------

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) {
        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) {
        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);
    }
}

// ---------------------------------------------------------
// Data Generation Suite
// ---------------------------------------------------------

enum class DataType {
    RANDOM,
    REVERSE_SORTED,
    NEARLY_SORTED_ASC,
    NEARLY_SORTED_DESC,
    MANY_DUPLICATES,
    ORGAN_PIPE
};

std::string getDataTypeName(DataType type) {
    switch (type) {
        case DataType::RANDOM: return "Random";
        case DataType::REVERSE_SORTED: return "Reverse Sorted";
        case DataType::NEARLY_SORTED_ASC: return "Nearly Sorted (Asc)";
        case DataType::NEARLY_SORTED_DESC: return "Nearly Sorted (Desc)";
        case DataType::MANY_DUPLICATES: return "Many Duplicates";
        case DataType::ORGAN_PIPE: return "Organ Pipe";
        default: return "Unknown";
    }
}

std::vector<int> generateData(DataType type, int size, std::mt19937& gen) {
    std::vector<int> arr(size);
    switch (type) {
        case DataType::RANDOM: {
            std::uniform_int_distribution<> dist(1, size * 10);
            for (int& x : arr) x = dist(gen);
            break;
        }
        case DataType::REVERSE_SORTED: {
            for (int i = 0; i < size; ++i) arr[i] = size - i;
            break;
        }
        case DataType::NEARLY_SORTED_ASC: {
            for (int i = 0; i < size; ++i) arr[i] = i;
            std::uniform_int_distribution<> dist(0, size - 1);
            // 5% noise factor
            for (int i = 0; i < size / 20; ++i) std::swap(arr[dist(gen)], arr[dist(gen)]);
            break;
        }
        case DataType::NEARLY_SORTED_DESC: {
            for (int i = 0; i < size; ++i) arr[i] = size - i;
            std::uniform_int_distribution<> dist(0, size - 1);
            // 5% noise factor
            for (int i = 0; i < size / 20; ++i) std::swap(arr[dist(gen)], arr[dist(gen)]);
            break;
        }
        case DataType::MANY_DUPLICATES: {
            std::uniform_int_distribution<> dist(1, 10); // Only 10 distinct values
            for (int& x : arr) x = dist(gen);
            break;
        }
        case DataType::ORGAN_PIPE: {
            for (int i = 0; i < size / 2; ++i) arr[i] = i;
            for (int i = size / 2; i < size; ++i) arr[i] = size - i;
            break;
        }
    }
    return arr;
}

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

int main() {
    const int NUM_ELEMENTS = 10000;
    const int NUM_TRIALS = 1000;

    std::random_device rd;
    std::mt19937 gen(rd());

    DataType types[] = {
        DataType::RANDOM, DataType::REVERSE_SORTED, DataType::NEARLY_SORTED_ASC,
        DataType::NEARLY_SORTED_DESC, DataType::MANY_DUPLICATES,
        DataType::ORGAN_PIPE
    };

    std::cout << "Starting benchmark suite (Array Size: " << NUM_ELEMENTS
              << ", Trials per pattern: " << NUM_TRIALS << ")\n";
    std::cout << std::string(105, '=') << std::endl;
    std::cout << std::left << std::setw(25) << "Data Pattern"
              << std::setw(25) << "| std::sort (s)"
              << std::setw(30) << "| Quick + Std Insert (s)"
              << std::setw(25) << "| Quick + Custom Jump (s)" << std::endl;
    std::cout << std::string(105, '-') << std::endl;

    for (DataType type : types) {
        double totalStdSort = 0, totalQuickStd = 0, totalQuickJump = 0;

        for (int t = 0; t < NUM_TRIALS; ++t) {
            std::vector<int> data1 = generateData(type, NUM_ELEMENTS, gen);
            std::vector<int> data2 = data1;
            std::vector<int> data3 = data1;

            // 1. Benchmark std::sort
            auto s3 = std::chrono::steady_clock::now();
            std::sort(data3.begin(), data3.end());
            auto e3 = std::chrono::steady_clock::now();
            totalStdSort += std::chrono::duration<double>(e3 - s3).count();

            // 2. Benchmark QuickSort + Standard Insertion
            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();

            // 3. Benchmark QuickSort + Custom Jump Sort
            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::is_sorted(data3.begin(), data3.end())) {
                std::cout << "CRITICAL ERROR: Array sorting failed on pattern: "
                          << getDataTypeName(type) << std::endl;
                return 1;
            }
        }

        // Print results for this data type
        std::cout << std::left << std::setw(25) << getDataTypeName(type)
                  << "| " << std::setw(23) << std::fixed << std::setprecision(6) << totalStdSort
                  << "| " << std::setw(28) << std::fixed << std::setprecision(6) << totalQuickStd
                  << "| " << std::setw(23) << std::fixed << std::setprecision(6) << totalQuickJump
                  << std::endl;
    }

    std::cout << std::string(105, '=') << std::endl;
    return 0;
}