#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <locale.h>

int selectionSort(int *arr, int size) /// Функция сортировки прямым выбором
{
    int min, temp; // для поиска минимального элемента и для обмена
    for (int i = 0; i < size - 1; i++)
    {
        min = i; // запоминаем индекс текущего элемента
        // ищем минимальный элемент чтобы поместить на место i-ого
        for (int j = i + 1; j < size; j++)  // для остальных элементов после i-ого
        {
            if (arr[j] < arr[min]) // если элемент меньше минимального,
                min = j;       // запоминаем его индекс в min
        }
        temp = arr[i];      // меняем местами i-ый и минимальный элементы
        arr[i] = arr[min];
        arr[min] = temp;    }
    return *arr;
}



void mergeSort(int *a, int l, int r)
{
    if (l == r) return; // границы сошлись
    int mid = (l + r) / 2; // определяем середину последовательности
    // и рекурсивно вызываем функцию сортировки для каждой половины
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);

    int i = l; // начало первого пути
    int j = mid + 1; // начало второго пути
    int *tmp = (int*)malloc(r * sizeof(int)); // дополнительный массив
    for (int step = 0; step < r - l + 1; step++) // для всех элементов дополнительного массива
    {
        // записываем в формируемую последовательность меньший из элементов двух путей
        // или остаток первого пути если j > r
        if ((j > r) || ((i <= mid) && (a[i] < a[j])))
        {
            tmp[step] = a[i];
            i++;
        }
        else
        {
            tmp[step] = a[j];
            j++;
        }
    }
    // переписываем сформированную последовательность в исходный массив
    for (int step = 0; step < r - l + 1; step++)
        a[l + step] = tmp[step];
        free(tmp);
}

int main() {
    float start1, start2, stop1, stop2;
    int *arr, *arr1, size;
    scanf("%d", &size);
    setlocale(LC_ALL, "Rus");

    arr = (int*)calloc(size, sizeof(int));
    srand(time(NULL));
    for (int i = 0; i < size; i++) {
        arr[i] = -50 + rand() % (101);
        printf("%d ", arr[i]);
    }
    arr1 = (int*)calloc(size, sizeof(int));
    printf("\n");
    for (int i = 0; i < size; i++) {
        arr1[i] = arr[i];
    }
    start1 = clock();
    selectionSort(arr, size);
    stop1 = clock();
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    start2 = clock();
    mergeSort(arr1, 0, size - 1); // вызываем функцию сортировки
    stop2 = clock();
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr1[i]);
    }

    printf("\n Время сортировки прямым выбором : %f\n", (stop1 - start1) / CLOCKS_PER_SEC);
    printf("\n Время сортировки слиянием: %f\n", (stop2 - start2) / CLOCKS_PER_SEC);

    getchar();
    getchar();
    free(arr);
}