The problem is:

Write a program that merges two lists (which are assumed to be already sorted ascending), returning a new, ascending sorted list. Manage a current index for each list to keep track of portions already processed. Starting lists should not be modified. If, for example, the content ofa is 1 4 9 16 and the content ofb is4 7 9 9 11, the program return a new list composed of the following values: 1 4 4 7 9 9 9 11 16. The methods sort() and sorted() must not be used."

I wrote the code below but the output is

[1, 2, 3, 3, 6, 12, 11, 13, 14, 22, 17, 22, 23, 33]

It didn't sort well. What should I do?

def slistunion():
    a=[1,3,12,13,22,33]
    b=[2,3,6,11,14,17,22,23]
    print("list a is",a)
    print("list b is",b)
    l=[]
    shorter=min(len(a),len(b))
    longer= max(len(a),len(b))
    for i in range(0,shorter):
        l.append(a[i])
        l.append(b[i])
    lenghtdiff= len(b)-len(a)
    if lenghtdiff>0:
        lenghtdiff= len(a)-len(b)
    for i in range (lenghtdiff,0):
        l.append(b[i])
        a.append(a[i])
        z=0
    for i in range(0,len(l)-1):
        if l[i]>l[i 1]:
            a=l[i]
            l[i]=l[i 1]
            l[i 1]=a

CodePudding user response：

A minor variation on the answer provided by @Robert that can reduce the number of iterations of the loop at the expense of an additional comparison (for equality):

a = [1, 4, 9, 16]
b = [4, 7, 9, 9, 11]

def mysort(a, b):
    i = 0
    j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            result.append(a[i])
            i  = 1
        elif a[i] == b[j]:
            result.append(a[i])
            result.append(b[j])
            i  = 1
            j  = 1
        else:
            result.append(b[j])
            j  = 1
    if i == len(a):
        result.extend(b[j:])
    if j == len(b):
        result.extend(a[i:])
    return result

print(mysort(a, b))

The rules are that you can't use either sort() or sorted() but that doesn't bar you from implementing your own sort. In which case (just for fun):

def bubble(_list):
    e = len(_list)
    while e > 1:
        es = 0
        for i in range(1, e):
            if _list[i-1] > _list[i]:
                _list[i-1], _list[i] = _list[i], _list[i-1]
                es = i
        e = es
    return _list

def mysort(a, b):
    return bubble(a   b)

print(mysort(a, b))

CodePudding user response：

To merge the lists, you need to look at the first element of each list, and add only the smaller one to the result list, then move to the next element in the list you took the element from.

You need to have a loop with a counter for each input list, and you go through both lists at a time, but only advance the counter for the list from which you took an element.

At the end, one list may still have elements left, so you add those to the combined list.

def sorted_list_union(a, b):
    combined = []
    a_index = 0
    b_index = 0
    while (a_index < len(a) and b_index < len(b)):
        if a[a_index] < b[b_index]:
            combined.append(a[a_index])
            a_index  = 1
        else:
            combined.append(b[b_index])
            b_index  = 1

    for i in range(a_index, len(a)):
        combined.append(a[i])
    for i in range(b_index, len(a)):
        combined.append(b[i])

    # The last loops above can also be changed to
    #    combined  = a[a_index:]
    #    combined  = b[b_index:]
    # but the above form may make it clearer what is going on.

    return combined

a = [1, 3, 12, 13, 22, 33]
b = [2, 3, 6, 11, 14, 17, 22, 23]
print(sorted_list_union(a, b))