Question

Write and test a merge function that uses a recursive algorithm to merge two sorted arrays of integers. Neither list contains duplicates, and the resulting list should not contain duplicates either.

Hint: You may want to call a helper function from merge.

PROGRAM: C

Answer 1

#include<stdio.h>

// Merges two sorted arrays avoiding duplicates and returns the size of merged array

// arr1 --> First array
// arr2 --> Second array
// merged_arr --> Array formed upon merging, the final array
// l1 --> Length of the first array
// l2 --> Length of the second array
// idx1 --> Current index of arr1 in recursion
// idx2 --> Current index of arr2 in recursion
// idx3 --> Current index of merged_arr in recursion
int merge(int arr1[], int arr2[], int merged_arr[], int l1, int l2, int idx1, int idx2, int idx3)
{
    
    // Both arrays exist
        if(idx1 < l1 && idx2 < l2)
        {
            // Element under consideration of first array is smaller than the second array 
                if(arr1[idx1] < arr2[idx2])
                {
                        // Element under consideration = arr1[idx1]
                        
                    // At least one element exists in the merged array
                    // and the last element added to merged array is equal
                    // to this element. So, skip it otherwise it would result in duplicates
                        if(idx3 >=1 && merged_arr[idx3-1] == arr1[idx1])
                                return merge(arr1,arr2,merged_arr,l1,l2,idx1+1,idx2,idx3);
                                
                        // Add this element to merged_arr 
                        else
                        {
                                merged_arr[idx3] = arr1[idx1];
                                return merge(arr1,arr2,merged_arr,l1,l2,idx1+1,idx2,idx3+1);
                        }
                }
                
        // If the element under consideration of second array is smaller than the first array 
                else
                {
                    // Element under consideration = arr2[idx2]
                    
                    // At least one element exists in the merged array
                    // and the last element added to merged array is equal
                    // to this element. So, skip it otherwise it would result in duplicates
                        if(idx3 >=1 && merged_arr[idx3-1] == arr2[idx2])
                                return merge(arr1,arr2,merged_arr,l1,l2,idx1,idx2+1,idx3);
                                
            // Add this element to merged_arr                   
                        else
                        {
                                merged_arr[idx3] = arr2[idx2];
                                return merge(arr1,arr2,merged_arr,l1,l2,idx1,idx2+1,idx3+1);
                        }
                }
        }
        
    // One of the array is exhausted (finished traversing)
        else
        {
            
            // The first array still remains 
                if(idx1 < l1)
                {
                    
                    // This element is equal to last element of merged_arr
                    // Skip it  
                        if(idx3 >= 1 && merged_arr[idx3-1] == arr1[idx1]) 
                                return merge(arr1,arr2,merged_arr,l1,l2,idx1+1,idx2,idx3);
                                
            // Add this element to merged_arr
                        else
                        {
                                merged_arr[idx3] = arr1[idx1];
                                return merge(arr1,arr2,merged_arr,l1,l2,idx1+1,idx2,idx3+1);
                        }
                }
                
        // The second array still remains               
                if(idx2 < l2)
                {
                    
                    // This element is equal to last element of merged_arr
                    // Skip it  
                        if(idx3 >= 1 && merged_arr[idx3-1] == arr2[idx2]) 
                                return merge(arr1,arr2,merged_arr,l1,l2,idx1,idx2+1,idx3);
                                
                        // Add this element to merged_arr
                        else
                        {
                                merged_arr[idx3] = arr2[idx2];
                                return merge(arr1,arr2,merged_arr,l1,l2,idx1,idx2+1,idx3+1);
                        }       
                }
        }
        
    // Returning the size of merged array       
        return idx3;
}

// Driver method
int main()
{
    // Size of array 1 and array 2
        int n1 = 5;
        int n2 = 3;
        int arr1[] = {1, 2, 3, 4, 5};
        int arr2[] = {1, 2, 10};
        
    // Declaring merged_arr of size n1 + n2     
        int merged_arr[n1+n2];
        
        int size = merge(arr1, arr2, merged_arr, n1, n2, 0, 0, 0);
        for(int i=0;i<size;i++)
            printf("%d ", merged_arr[i]);
            
        return 0;
}