Home >  Term: optimal merge
optimal merge

Merge n sorted sequences of different lengths into one output while minimizing reads. Only two sequences can be merged at once. At each step, the two shortest sequences are merged. Formal Definition: Let D=(n1, ... , nk) be the set of lengths of sequences to be merged. Take the two shortest sequences, ni, nj∈ D, such that n≥ ni and n≥ nj ∀ n∈ D. Merge these two sequences. The new set D is D' = (D - (ni, nj)) ∪ (ni+nj). Repeat until there is only one sequence.

0 0

Looja

  • GeorgeV
  •  (Gold) 1123 points
  • 100% positive feedback
© 2024 CSOFT International, Ltd.