Monday, April 28, 2014

Merging sorted arrays in C

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

/* Utility to spill the beans - print contents */
void spill(int *c, int len)
{
   int i;

   for (i = 0 ; i < len; i++)
      printf("%d ", c[i]);
   printf("\n");

}

/* The meat - If j index of second array crossed the maximum,
   of the second array, then populate with the first.
   Similarly, if the i index crossed the maximum of the first
   array, populate with the second.
   Else, populate the lesser of the two into the new array.
   For non-descending sort.
 */
int * mergesort(int A[], int la,  int B[], int lb)
{
    int i = 0, j = 0, k = 0;
    int *C = malloc(la + lb);

    while (i < la || j < lb)
    {
       if (j >= lb || (A[i] < B[j]))
       {
          C[k] = A[i];
          i++;
       }
       else
       {
          C[k] = B[j];
          j++;
       }
       k++;
    }
    return C;
}

int main()
{
    int A[] = {8, 9, 9, 10, 10, 11, 12, 14};
    int B[] = {5, 6, 13, 37};
    int *c;

    c = mergesort(A, sizeof(A)/sizeof(int), B, sizeof (B)/sizeof(B[0]));
    spill(c, sizeof(A)/sizeof(int) + sizeof (B)/sizeof(B[0]));
    return 0;
}

No comments:

Post a Comment