Sort Array Using Merge Sort

1#include <stdio.h>
2
3void merge(int arr[], int l, int m, int r) {
4    int n1 = m - l + 1;
5    int n2 = r - m;
6    
7    int L[n1], R[n2];
8    
9    for (int i = 0; i < n1; i++)
10        L[i] = arr[l + i];
11    for (int j = 0; j < n2; j++)
12        R[j] = arr[m + 1 + j];
13    
14    int i = 0, j = 0, k = l;
15    
16    while (i < n1 && j < n2) {
17        if (L[i] <= R[j]) {
18            arr[k] = L[i];
19            i++;
20        } else {
21            arr[k] = R[j];
22            j++;
23        }
24        k++;
25    }
26    
27    while (i < n1) {
28        arr[k] = L[i];
29        i++; k++;
30    }
31    
32    while (j < n2) {
33        arr[k] = R[j];
34        j++; k++;
35    }
36}
37
38void mergeSort(int arr[], int l, int r) {
39    if (l < r) {
40        int m = l + (r - l) / 2;
41        
42        mergeSort(arr, l, m);
43        mergeSort(arr, m + 1, r);
44        
45        merge(arr, l, m, r);
46    }
47}
48
49int main() {
50    int arr[] = {38, 27, 43, 3, 9, 82, 10};
51    int n = sizeof(arr) / sizeof(arr[0]);
52    
53    printf("Original array: ");
54    for (int i = 0; i < n; i++)
55        printf("%d ", arr[i]);
56    
57    mergeSort(arr, 0, n - 1);
58    
59    printf("\nSorted array:   ");
60    for (int i = 0; i < n; i++)
61        printf("%d ", arr[i]);
62    printf("\n");
63    
64    return 0;
65}