#include <iostream>
#include <algorithm>
#include <chrono>

const std::size_t SIZE = 3000;

// =====================================================================
// 1. C++14 Constexpr Array & Helpers
// =====================================================================
template <typename T, std::size_t N>
struct CXArray {
    T data[N];
    constexpr T& operator[](std::size_t i) { return data[i]; }
    constexpr const T& operator[](std::size_t i) const { return data[i]; }
    constexpr T* begin() { return data; }
    constexpr T* end() { return data + N; }
    constexpr const T* begin() const { return data; }
    constexpr const T* end() const { return data + N; }
};

template <typename T>
constexpr void cx_swap(T& a, T& b) {
    T tmp = a; a = b; b = tmp;
}

// =====================================================================
// 2. Algorithm 1: Insertion Sort (The Finisher)
// =====================================================================
template <typename T, std::size_t N>
constexpr void cx_insertion_sort(CXArray<T, N>& arr, int left, int right) {
    for (int i = left + 1; i <= right; ++i) {
        T key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// =====================================================================
// 3. Algorithm 2: Heapsort (The Fallback for bad Quicksort behavior)
// =====================================================================
template <typename T, std::size_t N>
constexpr void cx_sift_down(CXArray<T, N>& arr, int left, int length, int i) {
    while (true) {
        int largest = i;
        int left_child = 2 * i + 1;
        int right_child = 2 * i + 2;

        if (left_child < length && arr[left + left_child] > arr[left + largest]) {
            largest = left_child;
        }
        if (right_child < length && arr[left + right_child] > arr[left + largest]) {
            largest = right_child;
        }
        if (largest == i) break;

        cx_swap(arr[left + i], arr[left + largest]);
        i = largest;
    }
}

template <typename T, std::size_t N>
constexpr void cx_heap_sort(CXArray<T, N>& arr, int left, int right) {
    int length = right - left + 1;
    if (length <= 1) return;

    // Build Max Heap
    for (int i = length / 2 - 1; i >= 0; --i) {
        cx_sift_down(arr, left, length, i);
    }
    // Extract Max elements
    for (int i = length - 1; i > 0; --i) {
        cx_swap(arr[left], arr[left + i]);
        cx_sift_down(arr, left, i, 0); // Sift down with reduced heap size
    }
}

// =====================================================================
// 4. Algorithm 3: The Introsort Strategy (Quicksort Manager)
// =====================================================================
template <typename T, std::size_t N>
constexpr void cx_introsort_loop(CXArray<T, N>& arr, int left, int right, int depth_limit) {
    // STRATEGY 3: Stop early if partition is tiny. Leave it for Insertion Sort.
    if (right - left <= 16) {
        return; 
    }

    // STRATEGY 2: If recursion is too deep, switch to Heapsort to guarantee O(N log N)
    if (depth_limit == 0) {
        cx_heap_sort(arr, left, right);
        return;
    }

    // STRATEGY 1: Standard Quicksort Partitioning
    T pivot = arr[left + (right - left) / 2];
    int i = left;
    int j = right;
    
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        
        if (i <= j) {
            cx_swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }

    // Recurse with less depth limit
    if (left < j) cx_introsort_loop(arr, left, j, depth_limit - 1);
    if (i < right) cx_introsort_loop(arr, i, right, depth_limit - 1);
}

// The master wrapper that initiates the Strategy
template <typename T, std::size_t N>
constexpr CXArray<T, N> generate_introsort(CXArray<T, N> arr) {
    // Calculate recursion limit: 2 * log2(N)
    int depth_limit = 0;
    int n = N;
    while (n > 0) { 
        n >>= 1; 
        depth_limit++; 
    }
    depth_limit *= 2;

    // Phase 1: Heavy lifting (Quicksort + Heapsort fallback)
    cx_introsort_loop(arr, 0, N - 1, depth_limit);
    
    // Phase 2: Final cleanup (Insertion Sort on the 16-element chunks)
    cx_insertion_sort(arr, 0, N - 1);
    
    return arr;
}

// =====================================================================
// Compile-Time Evaluation Trigger
// =====================================================================
constexpr CXArray<int, SIZE> generate_random_data() {
    CXArray<int, SIZE> arr{};
    unsigned int seed = 98765;
    for (std::size_t i = 0; i < SIZE; ++i) {
        seed = (1103515245 * seed + 12345) % 2147483648; 
        arr[i] = seed % 100000;
    }
    return arr;
}

// 💥 COMPILER EXECUTES INTROSORT HERE 💥
constexpr auto unsorted_data = generate_random_data();
constexpr auto sorted_data = generate_introsort(unsorted_data);

// =====================================================================
// Benchmark Engine
// =====================================================================
int main() {
    std::cout << "Data Size: " << SIZE << " elements\n";

    // 1. Runtime Standard Sort
    CXArray<int, SIZE> runtime_data = unsorted_data; 
    
    auto start1 = std::chrono::high_resolution_clock::now();
    std::sort(runtime_data.begin(), runtime_data.end());
    auto end1 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> time_std = end1 - start1;

    // 2. Compile-Time Introsort (0ms)
    auto start2 = std::chrono::high_resolution_clock::now();
    volatile int dummy = sorted_data[0]; // Prevent optimization
    auto end2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> time_cx = end2 - start2;

    std::cout << "\n--- Benchmark Results ---\n";
    std::cout << "Runtime std::sort:            " << time_std.count() << " ms\n";
    std::cout << "Compile-Time Introsort:       " << time_cx.count() << " ms\n";

    bool correct = std::is_sorted(sorted_data.begin(), sorted_data.end());
    std::cout << "\nCompile-Time array is sorted correctly: " << (correct ? "True" : "False") << "\n";

    return 0;
}