Register | Sing In

New posts

Stacks in C programming Linked Lists in C programming File Input/Output in C programming Check prime numbers in C Programming C Programming Enumeration C Programming Union

Archives

2013-10 2013-09 2013-08

Merge Sort in C Programming

August 25, 2013 Posted by: GPA Views: 603 0 comments

Problem

Write program that sort integer array usign merge Sort in C.

Solution

This algorithm works based on divide and conquer rule. First it divides array in small arrays containing 1 or 2 elements. In the next steps it compare two arrays and than sort those two arrays. This picture shows how it works. A recursive merge sort algorithm used to sort an array of 8 integer values - {5, 1, 12, -5, 16, 2, 12, 14}.

step by step execution of merge sort

Example:

   

#include <stdio.h>
#include <stdlib.h>
int input_array[8] = {5, 1, 12, -5, 16, 2, 12, 14};
int input_arrayCopy[8];
int size=8;
void mergeSort(int start, int end);
void merge(int start, int middleofarray, int end);
int main(int argc, char *argv[])
{  
     int i,j,k;
     printf( "globalproganswer.com\n" );
     printf( "Array before Merge sorting:\n" );
     for ( i = 0; i < size; i++ ) {
        printf( "%d ",input_array[i]);
   }
   mergeSort(0, size-1);
    //show result after sorting
    printf("\n\nArray after Merge sorting:\n" );
    for ( i = 0; i < size; i++ ) {
       printf( "%d ",input_array[i]);
    }
    printf("\n");
   system("PAUSE");
    return 0;
}
void mergeSort(int start, int end) {
       int middleofarray = (start + end) / 2;
       if(start < end){
            mergeSort(start, middleofarray);
              printf("\n\nArray after Split from start to middleofarray\n" );
              int i;
              for (i = 0; i < 8; i++ ) {
                  printf( "%d ",input_array[i]);
              }
              mergeSort(middleofarray+1, end);
              printf("\n\nArray after Split from middleofarray + 1 to end:\n" );
              for (i = 0; i < 8; i++ ) {
                 printf( "%d ",input_array[i]);
              }
              merge(start, middleofarray, end);
              printf("\n\nArray after Sort & Merge the two arrays:\n" );
              for (i = 0; i < 8; i++ ) {
                printf( "%d ",input_array[i]);
              }
       }
}
void merge(int start, int middleofarray, int end) {
        int firstArrayStart = start;
        int secondArrayStart = middleofarray + 1;
        int i;
        for(i = start ; i <= end ; i ++){
             input_arrayCopy[i] = input_array[i];
        }
        while(secondArrayStart <= end && firstArrayStart <= middleofarray){
              if(input_arrayCopy[firstArrayStart] >= input_arrayCopy[secondArrayStart]){
                   input_array[start++] = input_arrayCopy[secondArrayStart++];
              }else{
                input_array[start++] = input_arrayCopy[firstArrayStart++];
              }
       }
       while(firstArrayStart <= middleofarray){
             input_array[start++] = input_arrayCopy[firstArrayStart++];  
       }
       while(secondArrayStart <= end){
           input_array[start++] = input_arrayCopy[secondArrayStart++];
      }
}

Output

Download this example

0 Comments...

Leave a Reply

Please, Sing In to leave a Reply for this material.



Online Chat

LiveZilla Live Help

Popular posts

Function strtok in C programming Check prime numbers in C Programming C Programming Union Linked Lists in C programming File Input/Output in C programming C Programming Enumeration

RSS-subscribe

New materials

Subscribe