---

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

using namespace std;

// --- ВСПОМОГАТЕЛЬНОЕ ---
void vivodd(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

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;
    cout << "Введите размер массива: ";
    cin >> n;

    int* original = new int[n]; // Обычный массив
    int* temp = new int[n];     // Обычный массив

    int choice;
    cout << "1) Ввести числа вручную\n";
    cout << "2) Заполнить случайными числами\n";
    cin >> choice;

    if (choice == 1) {
        cout << "Введите " << n << " чисел: ";
        for (int i = 0; i < n; i++) cin >> original[i];
    }
    else {
        for (int i = 0; i < n; i++) original[i] = rand() % 100;
        cout << "Заполнено случайными числами.\n";
    }

    cout << "\nИсходный массив:\n   ";
    vivodd(original, n);

    // 1. БЫСТРАЯ СОРТИРОВКА (Встроенная sort)
    coppy(original, temp, n);
    sort(temp, temp + n); // <-- Встроенная быстрая
    cout << "\n1. Быстрая сортировка (sort):\n   ";
    vivodd(temp, n);

    // 2. СОРТИРОВКА СЛИЯНИЯМИ (Встроенная stable_sort)
    coppy(original, temp, n);
    stable_sort(temp, temp + n); // <-- Встроенная слияниями
    cout << "\n2. Сортировка слияниями (stable_sort):\n   ";
    vivodd(temp, n);

    // 3. ПИРАМИДАЛЬНАЯ СОРТИРОВКА (Встроенная make_heap + sort_heap)
    coppy(original, temp, n);
    make_heap(temp, temp + n); // Строим кучу
    sort_heap(temp, temp + n); // Сортируем кучу
    cout << "\n3. Пирамидальная сортировка (make_heap + sort_heap):\n   ";
    vivodd(temp, n);

    delete[] original;
    delete[] temp;

    return 0;
}