CODEWITHSUNDEEP
pythonpython-3.xalgorithmsorting
Santiago
Santiago

Reputation: 125

Sorting lists without .sort or sorted, solution in linear time

I'm doing some beginner python homework and this savage question comes all of a sudden, i've spent a good amount of time researching but I haven't found anything useful tho i feel the answer might be simpler then what've found so far. The excercise:

# Given two lists sorted in increasing order, create and
# return a merged list of all the elements in sorted order.
# You may modify the passed in lists.
# The solution should work in "linear" time, making a single
# pass of both lists.
# Hint: Don't use `sort` or `sorted` -- they are not O(n)
# linear time and the two lists are already provided in
# ascending sorted order.

If you could please throw in some documentation about the subject i'd appreciate it, thanks.

Upvotes: 0

Views: 966

Answers (2)

Santiago
Santiago

Reputation: 125

Kept working on it and this is what i ended up with, seemed to work fine

def linear_merge(list1, list2):
    list = []
    while list1 and list2:
        if list1[0] > list2[0]:
            list.append(list2[0])
            list2.remove(list2[0])
        else:
            list.append(list1[0])
            list1.remove(list1[0])
    if list1:
        list += list1
    elif list2:
        list += list2
    return list

Upvotes: 1

Vishnu
Vishnu

Reputation: 162

Take 2 iterative variables i and j, one for each list and traverse it in the same loop.
Assume one list is A = [2,5,6,9] and the other is B = [1,4,7]. So keep i for the first list that is A and j for B an a new empty list C. Pseudocode is something like this -

i = 0
j = 0
C = list()
while(i<len(A) and j<len(B)):
    if(A[i]<B[j]):
        #Append the number to C
        C.append(A[i])
        i+=1
    elif(A[i]>B[j]):
        C.append(B[j])
        j+=1
    else:
        #Both equal, so add both to C
        C.append(A[i])
        C.append(B[j])
        i+=1
        j+=1

Now if either i or j is less than len(A) or len(B) respectively, then add all remaining elements of that array to the new array C. i.e if there are any more elements not added to C in either of the lists, then add them to the list C. You can check this by comparing i and j with the respective lengths of their lists.

For any more clarifications, let me know.

Upvotes: 1

Related Questions