Merge Sort in C

In this tutorial, we are going to see how to create a Merge Sort program in C. Merge Sort runs in O (n log n) time. It is very efficient. Merge Sort is a recursive algorithm used for merging which is based on the Divide and Conquer technique. An array of elements is divided into two smaller sub-arrays. Once these two arrays are released independently, they are able to produce the sorted array. The merging process can be performed recursively until there is only one element in the array.
100 Multiple Choice Questions In C Programming – Part 1This collection of 100 Multiple Choice Questions and Answers (MCQs) In C Programming : Quizzes & Practice Tests with Answer focuses on “C Programming”.  …Read More

 

Algorithm :

mergeSort(tab[], g, d)
If d > g
   1. Find the middle to divide the array into two halves m = (g + d) / 2.
   2. Call the mergeSort method for the first half.
   3. Call the mergeSort method for the second half.
   4. Merge the two halves sorted in steps 2 and 3.

Example : Merge Sort

 
 

Program To Implement Merge Sorting in C

#include <stdio.h>

void mergeSort(int i, int j, int arr[], int tmp[]) {
    if(j <= i){ return;}
  
    int m = (i + j) / 2;
    
	//sort the left half recursively
    mergeSort(i, m, arr, tmp);     
	//sort the right half recursively
    mergeSort(m + 1, j, arr, tmp); 

	//pg points to the beginning of the left sub-array
    int pg = i;     
	//pg points to the beginning of the right sub-array
    int pd = m + 1; 
	//counter
    int c;          

//we loop from i to j to fill each element of the final merged array
    for(c = i; c <= j; c++) {
		//the pointer of the left sub-array has reached the limit
        if(pg == m + 1) { 
            tmp[c] = arr[pd];
            pd++;
        }
		//the pointer of the right sub-array has reached the limit
		else if (pd == j + 1) {
            tmp[c] = arr[pg];
            pg++;
        }
		//the pointer of the left sub-array points to a smaller element
		else if (arr[pg] < arr[pd]) { 
            tmp[c] = arr[pg];
            pg++;
        }
		//the pointer of the right sub-array points to a smaller element
		else {  
            tmp[c] = arr[pd];
            pd++;
        }
    }

	//copy elements from tmp[] to arr[]
    for(c = i; c <= j; c++) {  
        arr[c] = tmp[c];
    }
}


int main() {
  int  nbr, i, arr[100], tmp[100];
 
  printf(" Enter the number of elements in the array: ");
  scanf("%d", &nbr);
 
  printf(" Enter %d integers: ", nbr);
 
  for (i = 0; i < nbr; i++)
    scanf("%d", &arr[i]);
 
  mergeSort(0, nbr-1, arr, tmp);
 
  printf("\n Sorted array: ");
  for(i = 0; i < nbr; i++){
     printf(" %4d", arr[i]);
  }
  printf("\n");
  return 0;
}

Output:

 Enter the number of elements in the array: 4
 Enter 4 integers: 9 2 8 1

 Sorted array:     1    2    8    9

 

MCQPractice competitive and technical Multiple Choice Questions and Answers (MCQs) with simple and logical explanations to prepare for tests and interviews.Read More