CODEWITHSUNDEEP
pythonalgorithmfolddivide-and-conquer
Xiaohe Dong
Xiaohe Dong

Reputation: 5023

Why divide and conquer is fast over reduce to solve merge K sorted list

I am using Approach 5: Merge with Divide And Conquer to solve the merge K sorted problem in leetcode. The algorithm is very fast and takes around 100ms. However, I don't understand why the reduce approach takes much slower runtime (4000+ms).

Here is the code diff:

# reduce
import functools
return functools.reduce(_mergeTwoLists, lists)

# divide and conquer
step = 1
while step < num:
   for i in range(0, num - step, step * 2):
       lists[i] = _mergeTwoLists(lists[i], lists[i + step])
   step *= 2
   return lists[0]

If the divide and conquer is running in parallel, I can understand why divide and conquer is faster, but I thought it should be still running linear, right ?

I also write another expensive version of merge to test the diff:

  def add(a, b):
       tmp = 0
       for i in range(1, 5000):
           tmp += i
       return a + b

This version running time of reduce and divide and conquer is almost identical.

Is there a merge K sorted list test case that reduce can't handle ? Is there something I am missing in divide and conquer ?

Upvotes: 0

Views: 365

Answers (1)

Paul Panzer
Paul Panzer

Reputation: 53089

The complexities of the two approaches are different. A two-fold merge is O(m+n) where m and n are the lengths of the two lists.

divide and conquer takes O(log N - log J) iterations (N = total number of elements, J = length of sublists we start with) each iteration is O(N) because each element is involved in exactly one merge -> total O(N (log N - log J))

reduce takes N/J - 1 steps of complexities O(2J), O(3J), O(4J). etc. so the total complexity is O(N^2 / J)

Note that the total number of two-fold merges is the same in both cases, the difference is that the divide-and-conquer ones are cheaper on average.

That is consistent with your observation that replacing two-fold merge with addition yields roughly equal run times, because the cost of addition is essentially independent of operands (I take it you are adding numbers, not lists?) especially when it is swamped by a burn-time-loop.

Upvotes: 0

Related Questions