Merge Two Sorted Arrays

[kevin]

   Merged Sorted Arrays

 This function takes two two sorted Integer (Numeric) and merged them into a new array.  

PlayBASIC Code: [Select]

   Size=100

   Dim Test1(Size)
   Dim Test2(Size)

   ; fill both arrays with some random integers between 0 and 1000
   for lp =0 to Size
         Test1(lp)=rnd(1000)
         Test2(lp)=rnd(1000)
   next

   ; Place a couple of value at the end of our arrays to check we're
   ; getting all the values in the merged output
   test1(Size) = 5000
   test2(Size) = 9999
   

   ;  Sort the Arrays 
   SortArray Test1(),0,Size
   SortArray Test2(),0,Size


   Dim Result(0)


   Result()=MergeSortedArrays(Test1(), Test2())

   Sync
   waitkey
   



Function MergeSortedArrays(a(), b())

  ; dim our arrat C() to hold both merged arrays
    A_Size  =getarrayelements(a())
    B_Size  =getarrayelements(b())



    ; output array total size
      C_Size = A_Size+B_Size+1
    Dim c(C_Size)

    ; Initialize variables to track the current position in each array
    i = 0
    j = 0
      for LP=0 to C_Size
         ; Check if the value in array A is
         ; smaller than the value in array B

         if a(i) < b(j) 
             ; Add the value from array A to the merged array
            c(lp) = a(i)
            i++ ; Move to the next element in array A

            ; Check if we're out of values in array A   
            if i>A_Size
               ; If so, we copy the rest of B() to C()
               For CopyLP = j to B_Size
                  LP++   
                  c(LP)=b(CopyLP)
               next

            endif
            
        Else 
              
              ; Otherwise, the value in array B is smaller
            ; Add the value from array B to the merged array
            c(lp) = b(j)
            j++ ; Move to the next element in array B

            ; Check if we're out of values in array B   
            if j>B_Size

               ; if so, we can copy the rest of A() to C()
               For CopyLP = i to A_Size
                  LP++   
                  c(lp)=a(CopyLP)
               next
            endif
            
        Endif

    next lp
    ; Return the merged array
EndFunction c() 

   Learn To Code How it Works:

   The function called MergeSortedArrays takes two sorted arrays, a and b, as input and returns a new array containing the merged and sorted values from both input arrays.

   The function starts by declaring a new array, c, to hold the merged values of the two input arrays. It then initializes three variables, i, j, and lp, which will be used to track the current position in each of the input arrays and to loop through the elements of the output array.

   The function then enters a FOR loop which will iterate lp from 0 to the size of the output array. Inside the loop, the function compares the current element of array a to the current element of array b. If the element from array a is smaller, it is added to the merged array and the i variable is incremented to move to the next element in array a. If the element from array b is smaller, it is added to the merged array and the j variable is incremented to move to the next element in array b.

  If the end of either array a or b is reached, the rest of the values in the other array are added to the output array in a separate FOR loop. Finally, the function returns the merged array c.