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

Question

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.

This is the "merge" operation in a "mergesort". Have i be the position in one list, and j the position in the other. Both start at 0. Every time you "take" an element, you increment the position. After you've reached the end of one list, you take everything from the other. — btilly
– btilly, Commented Nov 12, 2020 at 18:15

Vishnu · Accepted Answer · 2020-11-12 18:24:16Z

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.

Santiago · Accepted Answer · 2020-11-13 03:56:52Z

1

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

answered Nov 13, 2020 at 3:56

Santiago

12510 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related