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

// =====================================================================
// Custom Template Metaprogramming (Generic) Implementation of Sort
// Uses a standard recursive Quicksort pattern
// =====================================================================
template<typename RandomIt>
void custom_template_sort(RandomIt first, RandomIt last) {
    // Base case: if the range is 1 or 0 elements, it is already sorted
    if (first >= last - 1) return;
    
    // Choose a pivot (middle element)
    auto pivot = *(first + (last - first) / 2);
    
    auto left = first;
    auto right = last - 1;
    
    // Partitioning
    while (left <= right) {
        while (*left < pivot) left++;
        while (*right > pivot) right--;
        
        if (left <= right) {
            std::iter_swap(left, right);
            left++;
            right--;
        }
    }
    
    // Recursive calls
    if (first < right + 1) {
        custom_template_sort(first, right + 1);
    }
    if (left < last) {
        custom_template_sort(left, last);
    }
}

// =====================================================================
// Benchmark Engine
// =====================================================================
int main() {
    const int SIZE = 100000;
    
    std::cout << "Generating " << SIZE << " random elements...\n";
    std::vector<int> data_std(SIZE);
    
    // Generate random data
    std::mt19937 rng(42); // Fixed seed for reproducible results
    std::uniform_int_distribution<int> dist(1, 1000000);
    for(int i = 0; i < SIZE; ++i) {
        data_std[i] = dist(rng);
    }
    
    // Create an identical copy for the custom sort
    std::vector<int> data_custom = data_std; 

    // ---------------------------------------------------------
    // Benchmark 1: std::sort
    // ---------------------------------------------------------
    auto start1 = std::chrono::high_resolution_clock::now();
    std::sort(data_std.begin(), data_std.end());
    auto end1 = std::chrono::high_resolution_clock::now();
    
    std::chrono::duration<double, std::milli> time_std = end1 - start1;

    // ---------------------------------------------------------
    // Benchmark 2: Custom Template Sort
    // ---------------------------------------------------------
    auto start2 = std::chrono::high_resolution_clock::now();
    custom_template_sort(data_custom.begin(), data_custom.end());
    auto end2 = std::chrono::high_resolution_clock::now();
    
    std::chrono::duration<double, std::milli> time_custom = end2 - start2;

    // ---------------------------------------------------------
    // Results
    // ---------------------------------------------------------
    std::cout << "\n--- Benchmark Results (" << SIZE << " elements) ---\n";
    std::cout << "std::sort time:          " << time_std.count() << " ms\n";
    std::cout << "custom_template_sort:    " << time_custom.count() << " ms\n";
    
    // Verify that the custom sort actually worked
    bool correct = std::is_sorted(data_custom.begin(), data_custom.end());
    std::cout << "\nCustom sort is correct:  " << (correct ? "True" : "False") << "\n";
    
    // Speed comparison
    if (time_std.count() < time_custom.count()) {
        std::cout << "Result: std::sort is " 
                  << (time_custom.count() / time_std.count()) 
                  << "x faster than the custom implementation.\n";
    }

    return 0;
}