#include <stdio.h>

void combinar(int vector[], int inicio, int medio, int fin) {

    int i = inicio;
    int j = medio + 1;
    int k = 0;

    int temporal[100];

    while (i <= medio && j <= fin) {

        if (vector[i] <= vector[j]) {
            temporal[k] = vector[i];
            i++;
        } else {
            temporal[k] = vector[j];
            j++;
        }

        k++;
    }

    while (i <= medio) {
        temporal[k] = vector[i];
        i++;
        k++;
    }

    while (j <= fin) {
        temporal[k] = vector[j];
        j++;
        k++;
    }

    for (i = inicio, k = 0; i <= fin; i++, k++) {
        vector[i] = temporal[k];
    }
}

void mergeSort(int vector[], int inicio, int fin) {

    if (inicio < fin) {

        int medio = (inicio + fin) / 2;

        mergeSort(vector, inicio, medio);

        mergeSort(vector, medio + 1, fin);

        combinar(vector, inicio, medio, fin);
    }
}

void imprimir(int vector[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", vector[i]);
    }
    printf("\n");
}

int main() {

    int vector[] = {45, 12, 78, 34, 23, 9, 56};
    int n = 7;

    printf("Vector original:\n");
    imprimir(vector, n);

    mergeSort(vector, 0, n - 1);

    printf("Vector ordenado:\n");
    imprimir(vector, n);

    return 0;
}