Standard Insertion Sort

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

// Benchmark Code (Baseline: Insertion Sort Only)
// Contact Email [email protected]
// Created by I.A

// Configuration Constants
const int NUM_ELEMENTS = 32;
const int NUM_TRIALS = 1000000;

// Helper function to print vector (for debugging small sizes)
void printVector(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

/**
 * Standard Insertion Sort implementation.
 */
void insertionSort(std::vector<int>& arr, int low, int high) {
    // Traverse through all elements from the second element (low + 1) to high
    for (int i = low + 1; i <= high; ++i) {
        int key = arr[i];
        int j = i - 1;

        /* Move elements that are greater than key to one position ahead */
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        // Insert the key into its correct position
        arr[j + 1] = key;
    }
}

int main() {
    std::cout << "Starting Benchmark (Baseline: Insertion Sort Only)..." << std::endl;
    std::cout << "Elements per array: " << NUM_ELEMENTS << std::endl;
    std::cout << "Total Trials: " << NUM_TRIALS << std::endl;

    // Setup random number generation
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> distrib(1, 10000000);

    // Pre-allocate vector
    std::vector<int> data(NUM_ELEMENTS);
    std::chrono::duration<double> total_sort_duration(0);

    for (int t = 1; t <= NUM_TRIALS; ++t) {
        // 1. Generate Random Numbers (NOT TIMED)
        for (int i = 0; i < NUM_ELEMENTS; ++i) {
            data[i] = distrib(gen);
        }

        // 2. Start Timer (Start "Stopwatch")
        auto start = std::chrono::steady_clock::now();

        // 3. Run Insertion Sort (The only timed operation)
        insertionSort(data, 0, NUM_ELEMENTS - 1);

        // 4. Stop Timer (Stop "Stopwatch")
        auto end = std::chrono::steady_clock::now();

        // 5. Add difference to accumulator
        total_sort_duration += (end - start);

        // Progress logging and verification (for brevity, removed redundant check)
        if (t % 100000 == 0 || t == NUM_TRIALS) {
            std::cout << "Completed Trial " << t << "/" << NUM_TRIALS << "\r" << std::flush;
        }
    }

    std::cout << "\n\nBenchmark Complete." << std::endl;
    std::cout << "Total Sorting Time (Insertion Sort Only): " << total_sort_duration.count() << " seconds" << std::endl;
    std::cout << "Average Time per Sort: " << total_sort_duration.count() / NUM_TRIALS << " seconds" << std::endl;

    return 0;
}