What Is Merging?

Merging is a fundamental operation in computer science and data processing that combines two or more ordered sequences into a single sorted sequence while preserving the relative order of all elements. The operation is most commonly encountered as a building block of merge sort, the comparison-based sorting algorithm introduced by John von Neumann in 1945, but it is also central to database query processing, stream data integration, version control systems, and parallel computation. Merging is distinguished from sorting a combined set from scratch: it takes advantage of preexisting order in the input sequences to achieve linear time complexity in the simplest case.

The theoretical foundations of merging lie in the analysis of algorithms, where the merge operation is studied in terms of comparisons required, stability (preservation of equal-element order), and memory usage. Merging is closely related to sorting; the two problems are analyzed together in algorithm complexity literature, and many production systems alternate between them.

Merge Operations in Algorithms

The canonical two-way merge combines two sorted sequences of total length n using at most n-1 comparisons and O(n) additional memory. It works by maintaining a pointer into each sequence, repeatedly selecting and advancing the pointer to the smaller front element. This operation underpins merge sort, which recursively divides an array into halves, sorts each half, and merges them back, achieving O(n log n) worst-case time with guaranteed stability. Stability is a key reason merge sort is preferred over quicksort for sorting linked lists and for applications where equal records must preserve their original relative sequence.

Multi-way (k-way) merging combines k sorted runs simultaneously, typically using a min-heap of size k to identify the smallest available element across all runs. Multi-way merging is the merge step in external sorting, where data too large for main memory is processed in sorted chunks on disk and merged in a final pass. The IEEE Transactions on Knowledge and Data Engineering paper on speeding up external mergesort describes hybrid approaches that reduce I/O cost in this context.

External and Parallel Merging

External sorting workflows generate sorted runs on disk and merge them in one or more passes. Single-pass merging of k runs requires reading and writing all n records once, so minimizing the number of passes by maximizing k is a primary design objective for database storage engines. Buffer pool management, read-ahead scheduling, and the layout of runs on multiple disks all affect throughput.

Parallel merging distributes the merge workload across multiple processors or cores. Richard Cole's 1988 parallel merge sort algorithm, published in the SIAM Journal on Computing, demonstrated that merging can be accomplished in O(log n) parallel steps using n processors. Batcher's odd-even merge network, an earlier hardware-oriented approach, constructs a comparison network of depth O(log² n) that merges two sorted sequences with no serial bottleneck, and remains relevant for FPGA-based and GPU-based sorting pipelines.

Database and Stream Merging

In relational databases, the sort-merge join executes a join between two relations by sorting each on the join key and then merging the resulting sequences. This approach scales predictably with data volume and is preferred when both relations are large and lack supporting indexes. Research on sort-merge joins in multi-core database systems addresses how to exploit CPU cache hierarchy and SIMD instructions to accelerate the merge phase.

Stream processing systems merge ordered event streams from multiple sources to produce a unified timeline, a problem with additional constraints around out-of-order arrival and watermarking that extends classical merging into the domain of continuous data.

Applications

Merging has applications in a wide range of fields, including:

• Database query processing, particularly sort-merge joins and index intersection
• External sorting of large datasets in data warehousing and analytics pipelines
• Distributed file systems, where sorted file segments are merged during compaction
• Version control systems, where text merging reconciles concurrent edits to shared files
• Hardware sorting networks in FPGA and GPU architectures