C Program to Implement Merge Sort

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;
}

 

Leave a Comment

Your email address will not be published. Required fields are marked *