CODEWITHSUNDEEP
pythonmergesort
Schwager
Schwager

Reputation: 23

list index out of range in a merge and sort function

I tried writing a simple merge and sort function in python and got stuck after getting the following error-

List out of range.

I would appreciate if you could help me fix it and figure out how to avoid it. I have added the code below-

def merge(lst1, lst2):
    # Gets two sorted lists and returns one merged and sorted list
    merge_sorted = []
    i = 0
    j = 0
    len1 = len(lst1) - 1
    len2 = len(lst2) - 1
    while i < len1 or j < len2:
        if lst1[i] < lst2[j]:
            merge_sorted.append(lst1[i])
            i += 1
        elif lst1[i] > lst2[j]:
            merge_sorted.append(lst2[j])
            j += 1
        else:
            merge_sorted.append(lst1[i])
            merge_sorted.append(lst2[j])
            i += 1
            j += 1
    return merge_sorted

lst1 = [2, 4, 5, 6, 8]
lst2 = [1, 3, 7, 9, 0]
merge(lst1, lst2)

What I got:

IndexError                                Traceback (most recent call last)
<ipython-input-13-572aad47097b> in <module>()
     22 lst1 = [2, 4, 5, 6, 8]
     23 lst2 = [1, 3, 7, 9, 0]
---> 24 merge(lst1, lst2)

<ipython-input-13-572aad47097b> in merge(lst1, lst2)
      7     len2 = len(lst2) - 1
      8     while i < len1 or j < len2:
----> 9         if lst1[i] < lst2[j]:
     10             merge_sorted.append(lst1[i])
     11             i += 1

IndexError: list index out of range

Upvotes: 2

Views: 439

Answers (4)

Patrick Artner
Patrick Artner

Reputation: 51653

Your problem is the while condition:

while i < len1 or j < len2:

it should be and - if either of the conditoins are not true, you simple append the remainder of the non-empty list to your result and you are done.

Your current code still enters the while-body and checks if lst1[i] < lst2[j]: if one of the i / j is bigger then the list you get the error you have.

The full fixed code:

def merge(lst1, lst2):
    # Gets two sorted lists and returns one merged and sorted list
    merge_sorted = []
    i = 0
    j = 0
    len1 = len(lst1) - 1
    len2 = len(lst2) - 1
    while i < len1 and j < len2:         # use and
        if lst1[i] < lst2[j]:
            merge_sorted.append(lst1[i])
            i += 1
        elif lst1[i] > lst2[j]:
            merge_sorted.append(lst2[j])
            j += 1
        else:
            merge_sorted.append(lst1[i])
            merge_sorted.append(lst2[j])
            i += 1
            j += 1

    # add remainder lists - the slices evaluate to [] if behind the list lengths
    merge_sorted.extend(lst1[i:])  # if i is aready out of the list this is []
    merge_sorted.extend(lst2[j:]) # if j is aready out of the list this is []
    return merge_sorted

lst1 = [2, 4, 5, 6, 8]
lst2 = [0, 1, 3, 7, 9]  # fixed input, needs to be sorted, yours was not
print(merge(lst1, lst2))

Output:

[0, 1, 2, 3, 4, 5, 6, 8, 7, 9]

Upvotes: 6

Soroosh Noorzad
Soroosh Noorzad

Reputation: 468

First of all, Your logic is wrong! You are picking the lower numbers and putting them into the list. but what about the biggest number of all? You will be stuck there! Because you will never pick the last one!

I changed the logic. Instead of counting up the iterators, I removed the picked ones! and when one list got empty the rest of the other one will join the final list.

and secondly, don't use the "merge" name for your function! It's occupied!

def merger(l1, l2):
    merge_sorted = []
    t1, t2 = sorted(l1), sorted(l2)
    while len(t1) != 0 and len(t2) != 0:
        if t1[0] <= t2[0]:
            merge_sorted.append(t1[0])
            t1 = t1[1:]
        else:
            merge_sorted.append(t2[0])
            t2 = t2[1:]
    return merge_sorted + (t1 if len(t1) != 0 else t2)


lst2 = [2, 4, 5, 6, 8]
lst1 = [1, 3, 7, 9, 0, 10]
print(merger(lst1, lst2))

Upvotes: 2

venkatesh
venkatesh

Reputation: 162

As suggested by other techies you can modify and run the program but you are simply increasing the time complexity of your program which you could have done in two lines.

  • Just extend the list1 elements like

    list1.extend(list2)

  • once the elements are into the list1

    print(set(sorted(list1)))

Upvotes: 3

Shradha
Shradha

Reputation: 2442

Here are the values for i, j just before that if condition-

0 0
0 1
1 1
1 2
2 2
3 2
4 2
4 3
5 3

When any of the lists is traversed till the end, it throws index out of range error.

Solution-

Instead of using or condition, use and condition and append the remaining list elements at the end of the sorted list.

Upvotes: 1

Related Questions