main.c

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