merge_sort.c
sorting Implementation
59 lines1213 bytesC
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