list index out of range in a merge and sort function

Question

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)
 in ()
     22 lst1 = [2, 4, 5, 6, 8]
     23 lst2 = [1, 3, 7, 9, 0]
---> 24 merge(lst1, lst2)

 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

user_7505395 · Answer

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]

user_15433787 · Answer

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)))
```

user_4688639 · Answer

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))

user_9269273 · Answer

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

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.

list index out of range in a merge and sort function

4 Answers