(old) Modified Insertion Sort

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

// Benchmark Code (Modified: Rule + Insertion Sort)
// 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;
}

/**
 * Applies the specific rule requested for subarrays of size 3.
 */
void apply_three_element_rule(std::vector<int>& arr, int low, int high) {
    // The check for size 3 (high - low == 2) is assumed to pass
    // because the calling loop ensures it.

    int pivot = arr[low];
    int third_num = arr[high];

    if (third_num <= pivot) {
        // Swap all 3 to make pivot middle, third_num first
        int temp_mid = arr[low + 1];

        arr[high] = temp_mid;
        arr[low + 1] = pivot;
        arr[low] = third_num;
    } else {
        // Swap all 3 to make pivot middle, third_num last
        int temp_mid = arr[low + 1];

        arr[low] = temp_mid;
        arr[low + 1] = pivot;
        arr[high] = third_num;
    }
}

/**
 * Standard Insertion Sort implementation.
 */
void insertionSort(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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    std::cout << "Starting Benchmark (Exhaustive 3-Element Rule + Insertion Sort)..." << std::endl;
    std::cout << "Elements per array: " << NUM_ELEMENTS << std::endl;
    std::cout << "Total Trials: " << NUM_TRIALS << std::endl;
    std::cout << "NOTE: The three-element rule is now called on *every* group of 3 elements." << 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();

        // 3a. APPLY THE THREE-ELEMENT RULE TO ALL GROUPS OF THREE (TIMED)
        if (NUM_ELEMENTS >= 3) {
            for (int i = 0; i <= NUM_ELEMENTS - 3; i += 3) {
                apply_three_element_rule(data, i, i + 2);
            }
        }

        // 3b. Run Insertion Sort (TIMED)
        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
        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 (Rule Loop + Insertion Sort): " << total_sort_duration.count() << " seconds" << std::endl;
    std::cout << "Average Time per Sort: " << total_sort_duration.count() / NUM_TRIALS << " seconds" << std::endl;

    return 0;
}