CODEWITHSUNDEEP
python
Soumyadyuti Nandy
Soumyadyuti Nandy

Reputation: 3

Merging two sorted arrays in python

I am trying to merge two sorted arrays recursively, and I can merge the first few numbers until one pointer exits the array. There seems to be some problem with the base case not getting executed. I have tried to print the new_arr with the pointers for each recursive call to debug but cannot seem to find a solution. Here is my code:

new_arr= []
i= 0
j=0
def merge(arr1, arr2, i, j):
    #base case
    ##when arr1 pointer exits
    print(i,j, new_arr)
    if(i>len(arr1)-1):
        new_arr.append(arr2[j:])
        return new_arr
    ##when arr2 pointer exits
    if (j > len(arr2)-1):
        new_arr.append(arr1[i:])
        return new_arr

    if(arr1[i]<arr2[j]):
        new_arr.append(arr1[i])
        i+=1
        merge(arr1, arr2, i, j)
    elif(arr1[i]>=arr2[j]):
        new_arr.append(arr2[j])
        j+=1
        merge(arr1, arr2, i, j)
sortedarr = merge([1,9], [3,7,11,14,18,99], i, j)
print(sortedarr)

and here goes my output:

0 0 []
1 0 [1]
1 1 [1, 3]
1 2 [1, 3, 7]
2 2 [1, 3, 7, 9]
None

Upvotes: 0

Views: 313

Answers (2)

Frank Yellin
Frank Yellin

Reputation: 11289

Note that Python already has a built-in function that knows how to merge sorted arrays, heapq.merge.

list(heapq.merge((1, 3, 5,  7), (2, 4, 6, 8)))
[1, 2, 3, 4, 5, 6, 7, 8]

Upvotes: 1

trincot
trincot

Reputation: 350310

These are the issues:

  • new_arr.append(arr2[j:]) should be new_arr.extend(arr2[j:]). append is for appending one item to the list, while extend concatenates a second list to the first. The same change needs to happen in the second case.

  • As you count on getting the mutated list as a returned value, you should not discard the list that is returned by the recursive call. You should return it back to the caller, until the first caller gets it.

  • It is a bad idea to have new_arr a global value. If the main program would call the function a second time for some other input, new_arr will still have its previous values, polluting the result of the next call.

Although the first two fixes will make your function work (for a single test), the last issue would best be fixed by using a different pattern:

Let the recursive call return the list that merges the values that still needed to be analysed, i.e. from i and j onwards. The caller is then responsible of prepending its own value to that returned (partial) list. This way there is no more need of a global variable:

def merge(arr1, arr2, i, j):
    if i >= len(arr1):
        return arr2[j:]
    if j >= len(arr2):
        return arr1[i:]

    if arr1[i] < arr2[j]:
        return [arr1[i]] + merge(arr1, arr2, i + 1, j)
    else:
        return [arr2[j]] + merge(arr1, arr2, i, j + 1)

sortedarr = merge([1,9], [3,7,11,14,18,99], i, j)
print(sortedarr)

Upvotes: 2

Related Questions