Merge the two sorted arrays into one of the array of larger size

Problem Statement :

Given two sorted arrays, one of size N and second of size M+N.. Merge them into the larger array which contains N empty spaces at the end..

Example :

 Array 1 = {3,7,11,14,15,0,0,0,0} (Size : 5 + 4)
 Array 2 = {1,2,11,16} (Size : 4)

Result :
 Merged to  Array1 = {1,2,3,7,11,11,14,15,16}

Approach :


1.Start the loop from end to beginning
2. Track the tail indexes of the two arrays
3. After Merging the position is equal to arr1Tail+arr2Tail+1 (until both index reaches 0)
4. If the arr2Tail is larger than or equal to 0 after merging, adding the remaining values to the merged array

C# Code 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace MergeTwoSortedArray

{

    class Program

    {

        static void Main(string[] args)

        {

            int[] arr1 = new int[] { 1, 2, 2, 3, 4, 5,0,0,0,0,0};

            int[] arr2 = new int[] { 2, 2, 7 };

            merge(arr1, arr2, 5);

            for (int i = 0; i < arr1.Length; i++)

            {

                Console.Write(arr1[i] + ",");

            }

        }

       // Function Implementing Merge

     // arr1 is larger array and arr2 is smaller array

    // Usedindex is the index of the arr1 last valid value in arr1

        public static void merge(int[] arr1, int[] arr2, int usedIndex)

        {

            int longused = usedIndex;

            int shortarr = arr2.Length - 1;

            while (shortarr >= 0 && longused >= 0)

            {

                if (arr2[shortarr] > arr1[longused])

                {

                    arr1[shortarr + longused + 1] = arr2[shortarr];

                    shortarr--;

                }

                else

                {

                    arr1[shortarr + longused + 1] = arr1[longused];

                    longused--;

                }

            }

           while(shortarr >= 0)

            {

                arr1[shortarr] = arr2[shortarr];

                shortarr--;

            }                     

        }

    }

}

Complexity :

Computational Complexity : O(M+ N) 

Space Complexity : Constant