Merge sorted lists into new list

Question

So i need to write a program that merges two sorted lists into a new third sorted list and I can ONLY use operations of the ADT sorted list.

As with all my other assignments I start with pseudocode but I am in a funk tonight and can't wrap my head around some pseudocode for this.

I have written some pointers though: Create a new sorted list; while the two lists are not empty remove and compare them, to add one or the other to the new list. Stop when the lists are empty (but do think about what happens when one becomes empty before the other!).

Any and all help is very appreciated

EDIT: To let you know I am just looking for Pseudocode help NOT actual code

Answer 1

function merge (lista, listb) {

    toReturn = your 'third list'

    while lista and listb both still have elements {
        if lista's smallest element < listb's smallest element {
            add lista's smallest element to toReturn
            remove lista's smallest element
        } else {
            add listb's smallest element to toReturn
            remove listb's smallest element
        }
    }

    // if lista has no elements, this loop is skipped
    while lista still has elements { 
        add them to toReturn
    }

    // if listb has no elements, this loop is skipped
    while listb still has elements { 
        add them to toReturn
    }

    return toReturn

}