Just a quick note, using insights from the composition algorithm, it appears possible to further simplify merging:
- Instead of finding the input linearization with the best remaining prefix, it is possible to only consider prefixes of what remains of the original chunks the input linearizations had.
- Instead of trying the intersection of that best prefix with every prefix of what remains of the other linearization, it suffices to only consider prefixes aligning with the chunk boundaries of the remainder, or even of just the original chunk boundaries.