Algorithm for N-way merge

by

How about the following idea:

  1. Create a priority queue
  2. Iterate through each file f
    1. enqueue the pair (nextNumberIn(f), f) using the first value as priority key
  3. While queue not empty
    1. dequeue head (m, f) of queue
    2. output m
    3. if f not depleted
      1. enqueue (nextNumberIn(f), f)

Since adding elements to a priority queue can be done in logarithmic time, item 2 is O(N × log N). Since (almost all) iterations of the while loop adds an element, the whole while-loop is O(M × log N) where M is the total number of numbers to sort.

Assuming all files have a non-empty sequence of numbers, we have M > N and thus the whole algorithm should be O(M × log N).

More Related Contents:

  1. Algorithm for merging two max heaps?
  2. Find a pair of elements from an array whose sum equals a given number
  3. Find all paths between two graph nodes
  4. How do I calculate the area of a 2d polygon?
  5. What distribution do you get from this broken random shuffle?
  6. Hash table runtime complexity (insert, search and delete)
  7. How to get a square root for 32 bit input in one clock cycle only?
  8. Finding whether a point lies inside a rectangle or not
  9. recursion versus iteration
  10. How do Trigonometric functions work? [closed]
  11. What is an Efficient algorithm to find Area of Overlapping Rectangles
  12. How can I measure the similarity between two images? [closed]
  13. Mapping N-dimensional value to a point on Hilbert curve
  14. Find the paths between two given nodes?
  15. Finding all the shortest paths between two nodes in unweighted undirected graph
  16. Two Rectangles intersection
  17. Fastest primality test
  18. Efficient maths algorithm to calculate intersections
  19. How to calculate or approximate the median of a list without storing the list
  20. Sort Four Points in Clockwise Order
  21. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  22. Obfuscating an ID
  23. Algorithm for autocomplete?
  24. An inverse Fibonacci algorithm?
  25. Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
  26. Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location
  27. Compute the area of intersection between a circle and a triangle?
  28. Unbiased random number generator using a biased one
  29. Quadratic algorithm for 4-SUM
  30. CUDA stream compaction algorithm

Leave a Comment