C program to sort elements in an array using merge sort

      Conceptually, a merge sort works as follows

       1. Recursively divide the unsorted list into n sublists, each containing 1          element (a list of 1 element is considered sorted).

      2. Repeatedly merge sublists to produce new sorted sublists until there is only          1 sublist remaining. This will be the sorted list.

The fundamental operation in this algorithm is merging two sorted lists. The basic merging algorithm takes two input arrays a and b, an output array c, and three counters, aptr, bptr, and cptr, which are initially set to the beginning of their respective arrays. The smaller of a[aptr] and b[bptr] is copied to the next entry in c, and the appropriate counters are advanced. When either input list is exhausted, the remainder of the other list is copied to c. In this way, the merge sort sorts the contents of an array.

C program to sort elements in an array using merge sort



Source Code :

#include<stdio.h>
void mergesort(int [], int);
void merge ( int [], int [], int ,int [], int);
int main()
{
    int arr[50], n, key, index;
    printf("How many elements do you want to create the array with?(max 50): ");
    fflush(stdout);
    scanf("%d", &n);
    puts("Enter the array elements one by one \n");
    for (index = 0; index < n; index++)
        scanf("%d", &arr[index]);   //Step 1
   mergesort(arr, n);               //Step 2
   printf("\n The elements after sorting are...\n");
   for (index = 0; index < n; index++)
        printf("%d ", arr[index]);   //Step 3
   return 0;
}

void mergesort(int array[], int n) 
{ 
    int j,n1,n2,arr1[50],arr2[50]; 
    if (n<=1)
       return; 
    n1=n/2; 
    n2 = n - n1; 
    for ( j = 0; j < n1; j++ ) 
        arr1[j]= array[j]; 
    for ( j = 0; j < n2; j++ )
        arr2[j]= array[j+n1];
    mergesort(arr1, n1); 
    mergesort(arr2, n2); 
    merge(array, arr1, n1, arr2, n2); 
 }
 
void merge ( int array[], int arr1[], int n1,int arr2[], int n2) 
{ 
    int j, p=0, p1=0,p2=0; 
    printf("\n After merging [");
    for(j=0; j < n1; j++) 
    	printf("%d ",arr1[j] ); 
    printf("] [");
    for(j=0; j < n2; j++) 
    	printf("%d ",arr2[j] ); 
    printf("]"); 
    while ( p1 < n1 && p2 < n2 ) 
    { 
      	if( arr1[p1] < arr2[p2 ]) 
           array [p++] = arr1[p1++]; 
      	else 
           array[p++] = arr2[p2++]; 
    }
 
    while ( p1 < n1 ) 
      	array [p++] = arr1[p1++]; 
    while ( p2 < n2 ) 
      	array[p++] = arr2[p2++]; 
    printf(" merged array is [");
    for(j=0; j < n1+n2; j++) 
      printf("%d ",array[j] ); 
      printf("]\n"); 
}


edit-code-image

Sample Test cases :

1.  How many elements do you want to create the array with?(max 50): 4
    Enter the array elements one by one
    34
    78
    12
     1
   After merging [34 ] [78 ] merged array is [34 78 ]
   After merging [12 ] [1 ] merged array is [1 12 ]
   After merging [34 78 ] [1 12 ] merged array is [1 12 34 78 ]
   The elements after sorting are... 1  12  34  78

2. How many elements do you want to create the array with?(max 50): 3
   Enter the array elements one by one
   13
   56
   78
  After merging [56 ] [78 ] merged array is [56 78 ]
  After merging [13 ] [56 78 ] merged array is [13 56 78 ]
  The elements after sorting are... 13  56  78

Explanation:

Step 1: The elements of an array are read from the user using scanf() function.

Step 2: The function mergesort(arr,n) is called from the main program which sorts the elements of an array.

Step 3: After sorting the elements are printed on the output screen using printf() function.

More Insights:

1. More Information

Explore C Programs:C Programs