C Programming Challenge #04: Sorting - merge

Merge is type of sorting technique. It has good performance when large number of objects are sorted. Merge sort uses divide and combine approach.

Divide

• First the objects are divided into smaller sorting problem, so on till only one object is left to sort.
• Trivial solution when one object is left, Sorted one item is itself.

Combine

• After this combining start where each sorted array are combined to get a bigger sorted array.
• This is continued till the we get the whole array sorted.

Divide and combine can be depicted as in following diagram-

Strategy

1. Lets have all the number in array named a;
2. Lets have a macro Num_Elems that returns number of items in array a.
3. print_array is a utility function that will print the array items for us.
4. Implementing 1, 2, 3 are quite straight forward.
5. Lets implement the Divide part of the Merge sort algorithm in divide function.
1. To divide the array lets pass the pointer to start of array.
2. Start index and End Index
3. Hence the prototype will look as follows
4. int divide(int *a, int start, int end)
6. Combine part of the Merge sort algorithm is implemented in combine function.
1. To combine the array lets pass th pointer to start of array.
2. NOTE combine always involves combining adjacent array.
3. Hence only start, middle and end index are sufficient for combining.
4. Hence the prototype will look as follows
5. int combine(int *a, int start, int middle, int end) 

Hence our complete implementation of merge sort will look as follows.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define NUM_ELE(a) sizeof(a)/sizeof(a[0])

int divide(int *, int, int);
int combine(int *, int, int, int);
void print_array(int *, int);


int main()
{
   int i;
   int a[] = {4, 5, 1, 2, 5, 10, 1};
   printf("Unsorted Array is - ");
   print_array(a, NUM_ELE(a));
   printf("\n"); 

   divide(a, 0, NUM_ELE(a) - 1);

   printf("Sorted Array is - ");
   print_array(a, NUM_ELE(a));
   printf("\n"); 
}

int divide(int *a, int start, int end)
{
  int middle;

  if(start < end) {
     middle = (start + end) / 2;
     divide(a, start, middle);
     divide(a, middle + 1, end);
     combine(a, start, middle, end);
   }
   return 0;
}

int combine(int *a, int start, int middle, int end)
{
   int *L = malloc(sizeof(int) *  (middle - start +1));
   int *R = malloc(sizeof(int) * (end - middle));
   int i;
   int i_r, i_l;

   if( L == NULL || R == NULL) {
      printf("ERROR: malloc failed, may day !!!\n");
      exit(0);
   }

   /* Fill in L array */
   for(i = 0; i < middle - start + 1; i++) {
        L[i] = a[start + i];
   }
   L[i] = INT_MAX; /* Marking End of Array */

   /* Fill in R array */
   for(i = 0; i < end - middle ; i++) {
       R[i] = a[middle + i + 1];
    }
    R[i] = INT_MAX;  /* Marking End of Array */

    /* Combine from L and R and place it in a */
    i_l = i_r = 0;
    for(i = start; i <= end; i++) {
        if(L[i_l] <= R[i_r]) {
            a[i] = L[i_l++];
        }else {
            a[i] = R[i_r++];
        }
    }
    free(L);
    free(R);
}
void print_array(int *arr, int n)
{
   int i;
   for(i = 0; i < n; i++) {
      printf(" %d", arr[i]);
   }
}

Output of the program is

Unsorted Array is -  4 5 1 2 5 10 1
Sorted Array is -  1 1 2 4 5 5 10

Links

Next Article - C Programming Challenge #05: Sort - merge (without sentinels)
Previous Article - C Programming Challenge #03: Sort - selection
All Article - C Programming Challenge