C Programming Challenge #05: Sort - merge (without sentinels)

This is same as old merge sort C Programming Challenge #04: Sort - merge but not to use sentinels.

 In old sort in in the combine function.

/* 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 */

After copying in the L and R array we were marking the end of array using INT_MAX. Now Challenge is to re-write only the combine code without using the INT_MAX as sentinel.

For completeness i will show all other code with modification. But this time i won't explain other code you could refer to it here.

/* This is variation of Merge sort with No sentinels */

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

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

   i_l = i_r = 0;
   for(i = start; i <= end; i++) {
      if(L[i_l] <= R[i_r]) {
         /* See if L array is full,
            if Yes the copy from R array */
         if(i_l > middle - start) {
            a[i] = R[i_r++];
         } else {
            a[i] = L[i_l++];
         }
      }else {
         /* See if R array is full,
            if Yes the copy from R array */
         if(i_r >= end - middle) {
            a[i] = L[i_l++];
         }else {
            a[i] = R[i_r++];
         }
      }
   }
   free(L);
   free(R);
}

Output of above program is 

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

Changes are self explanatory!!!!

Links

Next Article - C Programming Challenge #06: Sort - insertion (using recursion)
Previous Article - C Programming Challenge #04: Sorting - merge

All Article - C Programming Challenge