---

8h, [18 мая 2026 в 00:12]
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include <iomanip>
#include <string>

using namespace std;

long long comparisons = 0; //счетчик для сравнения количесвта сравнений двух элементов в алгоритме
long long swaps = 0; // сколько раз алгоритм свапнул местами элементы

void selectionSort(vector<int>& arr) { // сорт выбором
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            comparisons++;
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
            swaps++;
        }
    }
}

void insertionSort(vector<int>& arr) { // сорт вставками
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            comparisons++;
            arr[j + 1] = arr[j];
            swaps++;
            j--;
        }
        if (j >= 0) comparisons++;
        arr[j + 1] = key;
    }
}

void bubbleSort(vector<int>& arr) { // сортировка пузырьком
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            comparisons++;
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swaps++;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

void Pyramid_supp(vector<int>& arr, int n, int i) { // вспомогат для пирамидальной
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n) {
        comparisons++;
        if (arr[left] > arr[largest]) largest = left;
    }
    if (right < n) {
        comparisons++;
        if (arr[right] > arr[largest]) largest = right;
    }

    if (largest != i) {
        swap(arr[i], arr[largest]);
        swaps++;
        Pyramid_supp(arr, n, largest);
    }
}

void Pyramid(vector<int>& arr) { //пирамидальная сорт
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; i--)
        Pyramid_supp(arr, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        swaps++;
        Pyramid_supp(arr, i, 0);
    }
}

const int RUN = 32; //делим массив на кускочки по 32 элемента

void insertionSortRange(vector<int>& arr, int left, int right) { //вставками для timsort для left and right
    for (int i = left + 1; i <= right; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            comparisons++;
            arr[j + 1] = arr[j];
            swaps++;
            j--;
        }
        if (j >= left) comparisons++;
        arr[j + 1] = key;
    }
}

void merge(vector<int>& arr, int left, int mid, int right) { //слияние
    vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;
    while (i < (int)leftArr.size() && j < (int)rightArr.size()) {
        comparisons++;
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        }
        else {
            arr[k++] = rightArr[j++];
            swaps++;
        }
    }
    while (i < (int)leftArr.size()) arr[k++] = leftArr[i++];
    while (j < (int)rightArr.size()) arr[k++] = rightArr[j++];
}

void timSort(vector<int>& arr) { //timsort сорт
    int n = arr.size();
    for (int i = 0; i < n; i += RUN)
        insertionSortRange(arr, i, min(i + RUN - 1, n - 1));
    for (int size = RUN; size < n; size *= 2) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = min(left + size - 1, n - 1);
            int right = min(left + 2 * size - 1, n - 1);
            if (mid < right)
                merge(arr, left, mid, right);
        }
    }
}