Join / union · All operations

Merge sorted tables

A variant of Append tables

Interleave tables already sorted on a key into one table that stays sorted on that key.

Status

In arcform

Runs as a SQL step

arcform carries it as a sql: step today.

The DuckDB step

Merge two sorted tables so the result stays sorted

SQL
-- both inputs are sorted on k, NULLs last
CREATE TEMP TABLE a AS SELECT * FROM (VALUES (1, 'a1'), (3, 'a2'), (3, 'a3'), (5, 'a4'), (NULL, 'a5')) t(k, v);
CREATE TEMP TABLE b AS SELECT * FROM (VALUES (2, 'b1'), (3, 'b2'), (4, 'b3'), (NULL, 'b4')) t(k, v);
-- stack, then order by the key; a tie keeps the first table's rows ahead of the second's
CREATE TEMP TABLE result AS
SELECT k, v FROM (SELECT 0 AS src, k, v FROM a UNION ALL SELECT 1, k, v FROM b) ORDER BY k NULLS LAST, src, v;
SELECT row_number() OVER () AS pos, * FROM result;
SELECT CASE WHEN ((SELECT list(v) = ['a1', 'b1', 'a2', 'a3', 'b2', 'b3', 'a4', 'a5', 'b4'] AND count(*) = 9 FROM result)
  AND (SELECT list(k) IS NOT DISTINCT FROM [1, 2, 3, 3, 3, 4, 5, NULL, NULL] FROM result)) THEN 'as expected' ELSE error('the merge should hold all 9 rows in key order 1, 2, 3, 3, 3, 4, 5, NULL, NULL with the rows of the first table first among equal keys') END AS verdict;
  • The statement builds its own data.
  • It needs nothing installed beyond DuckDB itself.
  • The statement checks its own result and raises an error when it is wrong: “the merge should hold all 9 rows in key order 1, 2, 3, 3, 3, 4, 5, NULL, NULL with the rows of the first table first among equal keys”.
  • It passed on DuckDB v2.0.0 (Cyanoptera) d54cbbe3df.

What other tools call it

Meridian's classification; an independent blind rating agreed on 95.7% of 324 rows (variant, version 3).

Apache Hop (2)
  • Sorted Mergeread 2026-09-27

    Merge several key-sorted streams into one sorted stream

  • Sorted schema mergeread 2026-09-27

    Merge pre-sorted streams of differing layouts into one sorted stream with a union schema

Pentaho Data Integration (1)
  • Sorted Mergeread 2026-09-27

    Merge several key-sorted input streams into one sorted stream

Polars (2)
  • DataFrame.merge_sortedread 2026-09-27

    Interleave two frames already sorted on a key into one sorted frame

  • merge_sortedread 2026-09-27

    Interleave several frames already sorted on a key into one sorted frame

Background

A merge algorithm takes several sorted lists as input and produces a single list holding all their elements in sorted order.[1] Merge algorithms are used as subroutines in sorting algorithms, most famously merge sort.[1]

When to use it

Reach for a sorted merge when every input already arrives in key order, such as logs by timestamp, and the combined table must keep that order. (Meridian's view) In Polars, it is the caller's responsibility to ensure the frames passed to merge_sorted are sorted in ascending order by the key, otherwise the output will not make sense.[2] Apache Hop's Sorted schema merge transform does not re-sort within each input stream; it only merges streams that are already sorted.[3]

In Polars, merge_sorted gives no guarantee over the output order of rows whose keys are equal unless maintain_order is set to True.[2] In Polars, merge_sorted with maintain_order set to True places rows from the left frame before rows from the right frame when their keys are equal.[2] In Apache Hop's Sorted schema merge transform, rows with equal sort keys keep a stable order based on the input stream index.[3] When ties matter, decide which input should come first among equal keys and say so, rather than relying on whichever order the tool happens to produce. (Meridian's view)

The method

Merging two sorted lists into one can be done in linear time.[1] The basic two-list merge repeatedly moves the smaller of the two lists' first elements to the output, then empties whichever list remains.[1] A k-way merge generalises binary merging to any number k of sorted input lists.[1] Keeping the k lists in a min-heap keyed by their first element lets a k-way merge of n elements run in O(n log k) time.[1] One external sorting algorithm divides its input into blocks that fit in memory, sorts them one by one and then merges the blocks.[1]

Apache Hop's Sorted Merge transform merges rows from multiple input transforms provided those rows are sorted themselves on the given key fields.[4]

Compared with the alternatives

Apache Hop's Append Streams transform reads from two transforms and processes the second stream only after the first one is finished.[5]

Sources

  1. [1]Merge algorithm - Wikipediasecondary source
  2. [2]polars.merge_sorted — Polars documentationdocumentation
  3. [3]Sorted schema merge | Apache Hopdocumentation
  4. [4]Sorted Merge | Apache Hopdocumentation
  5. [5]Append Streams | Apache Hopdocumentation