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.
- Sõnaliik: noun
- Valdkond/domeen: Computer science
- Category: Algorithms & data structures
- Government Agency: NIST
0
Looja
- GeorgeV
- 100% positive feedback