Merge Sort Algorithm

1#include <stdio.h>
2#include <stdlib.h>
3
4// Merge two subarrays of arr[]
5// First subarray is arr[left..mid]
6// Second subarray is arr[mid+1..right]
7void merge(int arr[], int left, int mid, int right) {
8    int i, j, k;
9    int n1 = mid - left + 1;
10    int n2 = right - mid;
11    
12    // Create temporary arrays
13    int* L = (int*)malloc(n1 * sizeof(int));
14    int* R = (int*)malloc(n2 * sizeof(int));
15    
16    // Copy data to temporary arrays L[] and R[]
17    for (i = 0; i < n1; i++)
18        L[i] = arr[left + i];
19    for (j = 0; j < n2; j++)
20        R[j] = arr[mid + 1 + j];
21    
22    // Merge the temporary arrays back into arr[left..right]
23    i = 0; // Initial index of first subarray
24    j = 0; // Initial index of second subarray
25    k = left; // Initial index of merged subarray
26    
27    while (i < n1 && j < n2) {
28        if (L[i] <= R[j]) {
29            arr[k] = L[i];
30            i++;
31        } else {
32            arr[k] = R[j];
33            j++;
34        }
35        k++;
36    }
37    
38    // Copy the remaining elements of L[], if any
39    while (i < n1) {
40        arr[k] = L[i];
41        i++;
42        k++;
43    }
44    
45    // Copy the remaining elements of R[], if any
46    while (j < n2) {
47        arr[k] = R[j];
48        j++;
49        k++;
50    }
51    
52    // Free the allocated memory
53    free(L);
54    free(R);
55}
56
57// Main function that sorts arr[left..right] using merge()
58void mergeSort(int arr[], int left, int right) {
59    if (left < right) {
60        // Same as (left+right)/2, but avoids overflow for large left and right
61        int mid = left + (right - left) / 2;
62        
63        // Sort first and second halves
64        mergeSort(arr, left, mid);
65        mergeSort(arr, mid + 1, right);
66        
67        // Merge the sorted halves
68        merge(arr, left, mid, right);
69    }
70}
71
72// Function to print an array
73void printArray(int arr[], int size) {
74    for (int i = 0; i < size; i++)
75        printf("%d ", arr[i]);
76    printf("\n");
77}
78
79int main() {
80    int arr[] = {38, 27, 43, 3, 9, 82, 10};
81    int n = sizeof(arr) / sizeof(arr[0]);
82    
83    printf("Original array: \n");
84    printArray(arr, n);
85    
86    mergeSort(arr, 0, n - 1);
87    
88    printf("Sorted array: \n");
89    printArray(arr, n);
90    
91    return 0;
92}