merge_sort.c

sorting Implementation

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