Merge Sort in C

 Merge Sort in C

Let us see how to implement Merge Sort in C Language.

What is Merge Sort?

Merge sort is a sorting algorithm that works on the divide and conquer approach. It divides an array into two parts and calls itself for these two halves. Then the two sorted parts of the array are merged together.

Given example explains the steps required in sorting.

In the above example, the array is divided recursively until its size becomes 1. After that it is merged together while being sorted. This is done until the final sorted array is obtained.

Source Code

The source code for Merge Sort is as follows:

#include < stdio.h > void merge(int arr[], int p, int q, int r) { int i, j, k; int n1 = q - p + 1; int n2 = r - q; int L[n1], R[n2]; for (i = 0; i < n1; i++) L[i] = arr[p + i]; for (j = 0; j < n2; j++) R[j] = arr[q + 1 + j]; i = 0; j = 0; k = p; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int p, int r) { if (p < r) { int q = (p + r) / 2; mergeSort(arr, p, q); mergeSort(arr, q + 1, r); merge(arr, p, q, r); } } int main() { int arr[] = { 5, 9, 1, 6, 3, 8 }; int n = 6; int i; printf("Implementing Merge Sort in C - Studyopedia\n"); printf("-------------------------------------------\n"); printf("Given array is \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); mergeSort(arr, 0, 5); printf("\nSorted array is \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); return 0; }

Output

The output obtained for the above code is: