Merging two sorted sequences

Input

1. Two sorted sequences, [math]\displaystyle{ S_{1} }[/math] and [math]\displaystyle{ S_{2} }[/math], that have identical component type.
2. A comparison on this component type.

Output

A sorted sequence [math]\displaystyle{ S }[/math], whose element set is the union of the element sets of [math]\displaystyle{ S_{1} }[/math] and [math]\displaystyle{ S_{2} }[/math], sorted according to the same definition of comparison.

Objective

N/A

Complexity

Linear in the sum of the lengths of the input sequences.

Known algorithms

Merge