merge_test.cpp

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <climits>
void printArray(int arr[], int size);

void merge(int *arr, int left, int mid, int right)
{

    int left_size = mid - left + 1;
    int right_size = right - mid;

    int left_sub_arr[left_size], right_sub_arr[right_size];

    for (int i = 0; i < left_size; left_sub_arr[i++] = arr[left + i])
        ; //i bax

    for (int j = 0; j < right_size; right_sub_arr[j++] = arr[mid + 1 + j])
        ; //je ye de bax

    int i = 0, j = 0, k = left;

    while (i < left_size && j < right_size)
    {
        if (left_sub_arr[i] <= right_sub_arr[j])

            arr[k] = left_sub_arr[i++];

        else

            arr[k] = right_sub_arr[j++];

        k++;
    }

    while (i < left_size)

        arr[k++] = left_sub_arr[i++];

    while (j < right_size)

        arr[k++] = right_sub_arr[j++];
}

void mergeSort(int *arr, int l, int r)
{
    if (l < r)
    {

        int m = (l + r) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

void test_merge_sort(int size)
{
    int *test = new int[size];

    srand(time(NULL));

    for (size_t i = 0; i < size; i++)
    {
        int r = rand() % USHRT_MAX;

        if (r % 9 == 0 || r % 31 == 0)
            r *= -1;

        test[i] = r;
    }

    std::cout<<"---------------------------------------------------------------------------------------\n";

    printArray(test, size);

    clock_t time=clock();

    mergeSort(test, 0, size - 1);

    time = clock() - time;

    std::cout<<"size:"<<size<<"\n";

    std::cout<<"time(sec):"<<(double)(double(time))/CLOCKS_PER_SEC<<"\n";

    printArray(test, size);

    std::cout<<"---------------------------------------------------------------------------------------\n";

    delete[] test;
}




int main()
{
    int size = 20;

    test_merge_sort(size);





    return 0;
}

void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}