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

void merge(int str[], int x ,int y,int z) {
    int i,j,k;
    int size1 = y - x +1;
    int size2 = z - y;
    int first[size1], second[size2];

    for (i=0;i<size1;i++) {
        first[i] =  str[x + 1];
    }

    for (j=0;j<size2;j++) {
        second[i] = str[y + 1 + j];
    }

    i = 0; j = 0; k = x;

    while (i < size1 && j < size2) {
        if(first[i] <= second[j]) {
            str[k] = first[i];
            i++;
        }
        else {
            str[k] = second[j];
            j++;
        }
        k++;
    }

    while (i < size1) {
        str[k] = first[i];
        i++;
        k++;
    }

    while (j < size2) {
        str[k] = second[j];
        j++;
        k++;
    }
}

void mergeSort(int str[], int x, int z) {
    if (x < z) {
        int y;

        y = x + (z - x) / 2;

        mergeSort(str, x, y);

        mergeSort(str, y + 1, z);

        merge(str, x, y, z);
    }
}
int main()
{
    int i,j,r;

    srand((int) time(NULL));

    int str[10];
    int str_size = (int) sizeof(str)/sizeof(str[0]);

    printf("\nDay so ngau nhien la: ");

    for(i=0;i<10;i++) {
        str[i] = rand();
        printf("%d ",str[i]);
    }

    mergeSort(str, 0, str_size - 1);

    printf("\n\nDay so da sap xep la: ");

    for (i=0;i < 10;i++) {
        printf("%d ", str[i]);
    }

    return 0;
}