Merging two pre-sorted lists with different lengths?-CodePudding

How do I merge two sorted lists with different lengths into one? The two lists are presorted, but i need to make sure they are still sorted after I put them together. I'm trying to fix my code, but using strictly what I have currently. No heap/sort/merge/zip, dictionaries etc.

EDIT: I am trying to append the items to an entirely new list. The end result should be new_list = [0, 1, 1, 3, 5, 5, 9, 9, 9]

My current program skips out of the remaining 9 in numbers2. If I switch the "and" to "or", the index goes out of range.

I've looked at other questions similar to this, but all the answers involve using other built in sorting methods, which I am trying to avoid.

def sort_numbers(list1, list2):
    new_list = []
    list1_index = 0
    list2_index = 0

    while list1_index != len(list1) and list2_index != len(list2):
        if list1[list1_index] < list2[list2_index]:
            new_list.append(list1[list1_index])
            list1_index  = 1
        else:
            new_list.append(list2[list2_index])
            list2_index  = 1
    return new_list


def main():
    numbers1 = [1, 3, 5, 5]
    numbers2 = [0, 1, 9, 9, 9]
    sorted_numbers = sort_numbers(numbers1, numbers2)
    print(sorted_numbers)


if __name__ == "__main__":
    main()

CodePudding user response：

Since your lists are already sorted, you can build something that compares only the first values in the list, and pops out the lower value until one of the lists is empty. All the elements of the list which is not empty then can simply be added to the end of the new list.

def sort_numbers(list1, list2):
    new_list = []
    
    while len(list1) > 0 and len(list2) > 0:
        if list1[0] <= list2[0]:
            new_list.append(list1.pop(0))
        else:
            new_list.append(list2.pop(0))
        
    return new_list   list1   list2

CodePudding user response：

You should just change that return statement to:

return new_list   list1[list1_index:]   list2[list2_index:]

At that moment there might be one of the two lists that still has values at (and after) their corresponding index, which should all be appended to the part that was already merged. One of the two extra terms will be an empty list (slice), but that doesn't matter. It is the other term that is important (whichever of the two it happens to be).