#include <iostream>
#include <ctime>

using namespace std;

void fillArray(int selectionArray[], int mergeArray[], int SIZE){
    for(int c = 0; c < SIZE; c++){
        srand((unsigned)time(0));
        selectionArray[c] = (rand() % 1000) + 1;
        mergeArray[c] = selectionArray[c];
    }
}

int selectionSort(int array[], int SIZE) {
    int i;
    int j;
    int indexSmallest;
    int temp;

    int count = 0;

    for (i = 0; i < SIZE - 1; ++i) {
        indexSmallest = i;
        for (j = i + 1; j < SIZE; ++j) {
            if (array[j] < array[indexSmallest]) {
                indexSmallest = j;
            }
        }
        temp = array[i];
        array[i] = array[indexSmallest];
        count++;
        array[indexSmallest] = temp;
        count++;
    }
    return count;
}

int merge(int array[], int i, int j, int k, int count) {
    int mergedSize;
    int mergePos;
    int leftPos;
    int rightPos;
    int* mergedNumbers = nullptr;

    mergePos = 0;
    mergedSize = k - i + 1;
    leftPos = i;
    rightPos = j + 1;
    mergedNumbers = new int[mergedSize];

    while (leftPos <= j && rightPos <= k) {
        if (array[leftPos] < array[rightPos]) {
            mergedNumbers[mergePos] = array[leftPos];
            ++leftPos;
            count++;
        }
        else {
            mergedNumbers[mergePos] = array[rightPos];
            ++rightPos;
            count++;
        }
        ++mergePos;
    }

    while (leftPos <= j) {
        mergedNumbers[mergePos] = array[leftPos];
        ++leftPos;
        ++mergePos;
        count++;
    }

    while (rightPos <= k) {
        mergedNumbers[mergePos] = array[rightPos];
        ++rightPos;
        ++mergePos;
        count++;
    }

    for (mergePos = 0; mergePos < mergedSize; ++mergePos) {
        array[i + mergePos] = mergedNumbers[mergePos];
    }
    return count;
}

int mergeSort(int array[], int i, int k) {
    int j;

    int count = 0;

    if (i < k) {
        j = (i + k) / 2;
        mergeSort(array, i, j);
        mergeSort(array, j + 1, k);

        count = count + merge(array, i, j, k, count);
    }
    return count;
}