k-Way Merge

\(k\)-Way Merge#

Contents#

\(k\)-way merge is useful for

  • merging \(k\) sorted arrays into a single sorted array

  • finding the \(k\)-th smallest (or largest) element in a number of sorted arrays

There are \(k\) arrays of length \(n\) sorted in ascending order.

SORTED_ARRAY_MERGE takes \(T(n) = \Theta(n)\) time.

The first merge operation takes two arrays of length \(n\) and requires \(\Theta(n)\) time.

The last merge operation takes an array of length \((k - 1)n\) and an array of length \(n\).

for i = 1 to kn         // kn times
    k - 1 comparisons   // k cost

Divide and conquer

divide: k/2-way merge combine: SORTED_ARRAY_MERGE

\(T(k, n) = 2T(k/2, n) + \Theta(n)\)

\(a = 2, b = 2, d = 1, 1 = \log_2 2\)

Acknowledgments#

Contents