In this Searching and Sorting in C, we will have a look at how to write a C Program to merge sort in C Program.

Merge sort (also commonly spelled mergesort) is an efficient, general-purpose sorting algorithm based on a comparison. Many implementations generate a consistent form, which means that input and output, the order of equal elements is the same. Merge sort is an algorithm of divide and conquer, invented by John von Neumann in 1945.

## Algorithm of Merge Sort

Step 1: [INITIALIZE] SET I = BEG, J = MID + 1, INDEX = 0 Step 2: Repeat while (I <= MID) AND (J<=END) IF ARR[I] < ARR[J] SET TEMP[INDEX] = ARR[I] SET I = I + 1 ELSE SET TEMP[INDEX] = ARR[J] SET J = J + 1 [END OF IF] SET INDEX = INDEX + 1 [END OF LOOP] Step 3: [Copy the remaining elements of right sub-array, if any] IF I > MID Repeat while J <= END SET TEMP[INDEX] = ARR[J] SET INDEX = INDEX + 1, SET J = J + 1 [END OF LOOP] [Copy the remaining elements of left sub-array, if any] ELSE Repeat while I <= MID SET TEMP[INDEX] = ARR[I] SET INDEX = INDEX + 1, SET I = I + 1 [END OF LOOP] [END OF IF] Step 4: [Copy the contents of TEMP back to ARR] SET K = 0 Step 5: Repeat while K < INDEX SET ARR[K] = TEMP[K] SET K = K + 1 [END OF LOOP] Step 6: Exit

## C Program to Implement Merge Sort

#include<stdlib.h> #include<stdio.h> void merge_function(int arr[], int l, int m, int r) { int i, j, k; int number_one = m - l + 1; int number_two = r - m; /* create temp arrays */ int L[number_one], R[number_two]; /* Copy data to temp arrays L[] and R[] */ for (i = 0; i < number_one; i++) L[i] = arr[l + i]; for (j = 0; j < number_two; j++) R[j] = arr[m + 1+ j]; /* Merge the temp arrays back into arr[l..r]*/ i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray while (i < number_one && j < number_two) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; k } else { arr[k] = R[j]; j++; } k++; } while (i < number_one) { arr[k] = L[i]; i++; k++; } while (j < number_two) { arr[k] = R[j]; j++; k++; } } void mergeSort(int arr[], int l, int r) { if (l < r) { int m = l+(r-l)/2; mergeSort(arr, l, m); mergeSort(arr, m+1, r); merge_function(arr, l, m, r); } } void printArray(int A[], int size) { int i; for (i=0; i < size; i++) printf("%d ", A[i]); printf("\n"); } /* Main program to test above functions */ int main() { int arr[] = {15, 10, 12, 4, 5, 6}; int arr_size = sizeof(arr)/sizeof(arr[0]); printf("Given array is \n"); printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); printf("\nHere are the sorted array \n"); printArray(arr, arr_size); return 0; }