// merge_sort.c

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {

    int i, j, k;

    int n1 = mid - left + 1;

    int n2 = right - mid;

    // Temporary arrays

    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]

    for(i = 0; i < n1; i++)

        L[i] = arr[left + i];

    for(j = 0; j < n2; j++)

        R[j] = arr[mid + 1 + j];

    // Merge the temp arrays back into arr[l..r]

    i = 0; j = 0; k = left;

    while(i < n1 && j < n2) {

        if(L[i] <= R[j])

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

        else

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

    }

    // Copy remaining elements of L[], if any

    while(i < n1)

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

    // Copy remaining elements of R[], if any

    while(j < n2)

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

}

void mergeSort(int arr[], int left, int right) {

    if(left < right) {

        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);

    }

}

void printArray(int arr[], int size) {

    for(int i = 0; i < size; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

int main() {

    int arr[] = {38, 27, 43, 3, 9, 82, 10};

    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array

}