---

#include <iostream>
#include <cstdlib>  
#include <ctime>   
#include <algorithm> // Для sort, stable_sort, make_heap, sort_heap

using namespace std;

// --- ВСПОМОГАТЕЛЬНОЕ ---
void coppy(int from[], int to[], int n) {
    for (int i = 0; i < n; i++) to[i] = from[i];
}

int main() {
    setlocale(LC_ALL, "Russian");
    srand(time(0));

    int n = 600000; 

    int* original = new int[n];
    int* temp = new int[n];

    for (int i = 0; i < n; i++) original[i] = rand() % 1000000;

    cout << "Размер массива: " << n << "\n\n";
    cout << "===== РЕЗУЛЬТАТЫ ЗАМЕРА (ВСТРОЕННЫЕ ФУНКЦИИ) =====\n";

    clock_t start, end;
    double time_spent;

    // 1. Быстрая
    coppy(original, temp, n);
    start = clock();
    sort(temp, temp + n);
    end = clock();
    time_spent = double(end - start) / CLOCKS_PER_SEC;
    cout << "1. Быстрая (sort):               " << time_spent << " сек.\n";

    // 2. Слияниями
    coppy(original, temp, n);
    start = clock();
    stable_sort(temp, temp + n);
    end = clock();
    time_spent = double(end - start) / CLOCKS_PER_SEC;
    cout << "2. Слияниями (stable_sort):      " << time_spent << " сек.\n";

    // 3. Пирамидальная
    coppy(original, temp, n);
    start = clock();
    make_heap(temp, temp + n);
    sort_heap(temp, temp + n);
    end = clock();
    time_spent = double(end - start) / CLOCKS_PER_SEC;
    cout << "3. Пирамидальная (make/sort_heap): " << time_spent << " сек.\n";

    delete[] original;
    delete[] temp;

    return 0;
}