# Merging two sorted sequences

## Input

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

## Output

A sorted sequence [math]S[/math], whose element set is the union of the element sets of [math]S_{1}[/math] and [math]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.