6
\$\begingroup\$

I am trying to implement a merge of two sorted lists of integers in Python using only the basic list abstract data type operations. That is, I do not want to use sorted() which comes with Python.

Could someone tell me if this code is alright? Also, am I correct to understand that it is linear to the core? That is, it uses no Python operation that is non-linear in time?

 def mergeSortedLists(list1, list2):
     list3 = []
     while list1 and list2:
         if list1[len(list1) - 1] > list2[len(list2) - 1]:
             list3.append(list1.pop())
         else:
             list3.append(list2.pop())
     return list3 + list1 + list2
\$\endgroup\$
0

2 Answers 2

Reset to default
7
\$\begingroup\$

Correctness

First of all, your merging code is not correct. If you have list1 = [1, 2, 3] and list2 = [4, 5, 6], the result would be [6, 5, 4, 1, 2, 3].

Assuming, you are up to [1, 2, 3, 4, 5, 6], you should be comparing the first elements of the lists. The problem with that is that "pop" from the left is an expensive operation for a regular Python list. Switching to the collections.deque double-ended queue would solve it - popleft() is O(1).

Fixed version:

from collections import deque


def merge_sorted_lists(left, right):
    """
    Merge sort merging function.
    TODO: Improve, add examples."""
    result = deque()

    left = deque(left)
    right = deque(right)

    while left and right:
        if left[0] > right[0]:
            result.append(right.popleft())
        else:
            result.append(left.popleft())
    return result + left + right

Time Complexity Analysis (for your "incorrect" version)

You are operating Python lists, according to the Time Complexity page:

  • the "get length" operation is O(1) (even though you can use -1 in place of len(list1) - 1 and len(list2) - 1)
  • the "pop from the right" operation is O(1)
  • the "append to the right" operation is O(1)

Which leads to overall complexity as O(N + M) where N is the length of the list1 and M - the length of the list list2.

Stylistic issues:

  • as per PEP8 guide, use 4 spaces for indentation
  • the function name should be merge_sorted_lists according to PEP8 variable naming guidelines
  • list1 should be better called left, list2 - right, list3 - result for clarity purposes
  • missing docstring explaining what function does
\$\endgroup\$
5
  • \$\begingroup\$ Am I correct to think that pop() is O(1) and pop(1) is O(n)? \$\endgroup\$ Commented Feb 7, 2017 at 21:13
  • \$\begingroup\$ Also, are we not assuming that the two list parameters have the same direction of sort (ascending or descending)? In your counter example you pick different directions. \$\endgroup\$ Commented Feb 7, 2017 at 21:15
  • \$\begingroup\$ @MadPhysicist exactly, popping from the left side of a list would require the list to be reallocated. \$\endgroup\$ Commented Feb 7, 2017 at 21:15
  • 1
    \$\begingroup\$ @MadPhysicist ah, my bad - that was a typo - the lists are [1, 2, 3] and [4, 5, 6], same direction, sorry. \$\endgroup\$ Commented Feb 7, 2017 at 21:16
  • \$\begingroup\$ I implemented the code using only lists. Could you take a look? \$\endgroup\$ Commented Feb 7, 2017 at 22:19
1
\$\begingroup\$

Here is a working implementation of the merge using only lists which (I think) functions linearly in time.

def mergeLists(a,b, direction):
         c = []
         # assuming ascending sortedness
         if direction == True:
             while a and b:
                 if a[len(a)-1] > b[len(b)-1]:
                     c.append(a.pop())
                 else:
                     c.append(b.pop())
             return (c + a[::-1] + b[::-1])[::-1]
         #assuming descending sortedness
         else:
             while a and b:
                 if a[len(a)-1] < b[len(b)-1]:
                      c.append(a.pop())
                 else:
                      c.append(b.pop())
             return (c+a[::-1]+b[::-1])[::-1]
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.