Merging two sorted sequences

From Algowiki
Jump to: navigation, search

Input

  1. Two sorted sequences, [math]S_{1}[/math] and [math]S_{2}[/math], that have identical component type.
  2. 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.

Known algorithms

Merge