How can I make it more efficient? (Merging arrays in C)

Question

It is assumed that the program will combine the two arrays and put them in the output array. I have:

void Merge(int *arr1, int *arr2, int *output, int arr1size, int arr2size) { 
   int arr2count = 0, arr1count = 0;                                        
   while (arr1count < arr1size) {                                           
      if (arr2count >= arr2size) {   /* dump arr1 because arr2 is done */                                         
         *output++ = *arr1++;                                               
         arr1count++;                                                       
      }                                                                     
      else if (*arr1 < *arr2) {                                             
         *output++ = *arr1++;                                               
         arr1count++;                                                       
      }                                                                     
      else {                                                                
         *output++ = *arr2++;                                               
         arr2count++;                                                       
      }                                                                     
   }                                                                        
   while (arr2count++ < arr2size) {    /* dump arr2 */                                     
      *output++ = *arr2++;                                                  
   }                                                                        
}

How can I make it more efficient? I mean, literally break any bit of code to make it a bit more efficient.

For argumentation, consider a less efficient triple loop implementation (shown below).

while (arr1count < arr1size && arr2count < arr2size) { .... }
while (arr1count < arr1size) { .... }
while (arr2count < arr2size) { .... }

Also, this should use pointer notation, not array notation (I want ...)

Answer 1

I tried to remove variables and increments. Note that these are minor improvements, while the algorithm still takes O (m + n) time.

: , 2048454

Edit2: while memcpy.Thanks to FUZxxl

void Merge2(int *arr1, int *arr2, int *output, int *a1last, int *a2last) { 
   while (arr1 < a1last && arr2 < a2last) {
      if (*arr1 < *arr2) {                                             
         *output++ = *arr1++;                                                
      }                                                                     
      else {                                                                
         *output++ = *arr2++;                                               
      }                                                                     
   }                  
   /* Replaced while with memcpy () */
   memcpy(output,arr1,sizeof(int)*(a1last-arr1));
   memcpy(output,arr2,sizeof(int)*(a2last-arr2));                                                  
   }                                                                        
}

int main()
{
    int a[]={1,3,5,7};
    int b[]={2,4,6,8};
    int c[10];
    int i;
    Merge2(a,b,c,&a[4],&b[4]); //&a[4] points to the end address of the array. Do not access value at that address, it is "out of bounds"

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

    printf("\n");

    return 0;
}

Answer 2

- ?

void Merge(int *arr1, int *arr2, int *output, int arr1size, int arr2size) {
  for (int i=0,i1=0,i2=0; i<arr1size+arr2size; i++) {
    if      (i1==arr1size) *output++ = *arr2++;
    else if (i2==arr2size) *output++ = *arr1++;
    else if (*arr1<*arr2)  *output++ = *arr1++, i1++;
    else                   *output++ = *arr2++, i2++;
  }
}

Answer 3

, , .

- , , , arr1count/arr2count : arr1last/arr2last

:

"arr1last = arr1 + arr1size" "arr2last = arr2 + arr2size"

, (- * count - * size ++ * last), arr1 < arr1last. arr2

Also your first one, if true, will always be true, so depending on the size of your arrays, it may cost to break out at this point and go with the triple loop implementation that you mentioned, because the above loop implementation may be ineffective if arr2size = 1 , arr1size = 999 and arr2 [0] will be among the first values ​​in 'output'