CODEWITHSUNDEEP
pythonalgorithmsortingtime-complexitymergesort
Zazaeil
Zazaeil

Reputation: 4119

Iterative merge sort?

I am aware of classical recursive approach to sort something by merging. It yields O(n * log(n)) complexity, which can be more or less easily shown via recurrence relation.

I've tried to reimplement merge sort in iterative fashion:

def atomize(l):
    return list(
        map(
            lambda x: [x],
            l if l is not None else []
        )
    )

def merge(l, r):
    res = []
    while (len(l) + len(r)) > 0:
        if len(l) < 1:
            res += r
            r = []
        elif len(r) < 1:
            res += l
            l = []
        else:
            if l[0] <= r[0]:
                res.append(l.pop(0))
            else:
                res.append(r.pop(0))
    return res

def iter_merge_sort(l):
    atoms = atomize(l) # O(n)
    while len(atoms) > 1: # O(n - 1)
        atoms.append(merge(atoms.pop(0), atoms.pop(0)))
    return atoms[0]

...and feels like I am mistaken somewhere, yet I fail to notice exact place. Recursive merge sort splits problem unless list of unsorted values reduces to a list of singletons - single elements that can be compared. That's what atomize(...) does: given a list, produces a list of lists-singletons (order O(n)).

Obviously, merge(...) is O(n) as well: ignore for moment that no linked lists are used for concatenation, that's not important here.

Finally.. the while block in the iter_merge_sort(...) itself takes exactly n - 1 repetitions, each of which costs at most O(n). Hence, I took O(n * log(n)) algorithm and "improved" it to be (n - 1) * n ~ O(n * n). Where is my mistake?

Upvotes: 5

Views: 752

Answers (1)

blhsing
blhsing

Reputation: 106553

Your algorithm is entirely correct. The problem lies in that you're using list.pop(0) as a way to dequeue, which costs O(n) in Python since all items after a popped item of a list have to be copied to the preceding positions.

You can use collections.deque in place of list so that you can use the deque.popleft method, which costs O(1):

from collections import deque

def atomize(l):
    return deque(
        map(
            lambda x: deque([x]),
            l if l is not None else []
        )
    )

def merge(l, r):
    res = deque()
    while (len(l) + len(r)) > 0:
        if len(l) < 1:
            res += r
            r = deque()
        elif len(r) < 1:
            res += l
            l = deque()
        else:
            if l[0] <= r[0]:
                res.append(l.popleft())
            else:
                res.append(r.popleft())
    return res

def iter_merge_sort(l):
    atoms = atomize(l) # O(n)
    while len(atoms) > 1: # O(n - 1)
        atoms.append(merge(atoms.popleft(), atoms.popleft()))
    return list(atoms[0])

so that:

iter_merge_sort([3,5,1,6,2,1])

returns:

[1, 1, 2, 3, 5, 6]

Upvotes: 2

Related Questions