Sortmerge

Sortmerge refers to a family of algorithms that combine sorting with a merging phase to produce a sorted sequence or to perform efficient joins on large data sets. The core idea is to first arrange data into sorted runs and then merge those runs to create a fully ordered result. This approach is especially prevalent in external sorting, where data exceeds main memory.

In external sorting, data is divided into chunks that fit in memory, each chunk is sorted in memory, and the sorted chunks are written to disk as runs. A subsequent multiway merge combines the runs, often in several passes, until a completely sorted file is produced. The performance of sort-merge external sort depends on the number of passes and the efficiency of merging, with the I/O cost typically dominating. The method is robust to varying memory sizes and is well suited to streaming large datasets.

In database systems, sort-merge joins use a similar idea to join two relations on a common key. Both input relations are sorted on the join attribute, and a linear-time merge is performed to produce matching pairs. Sort-merge join is particularly effective when the relations are already sorted, when there are no suitable indexes, or when the dataset is too large to fit entirely in memory. It can accommodate duplicates and works well with sequential I/O patterns, minimizing random disk seeks.

Variations emphasize stability (preserving the original order of equal elements), multiway merging, and adaptations for parallel or distributed environments. Overall, sortmerge is valued for its simplicity and efficiency in handling large-scale sorting and joining tasks. See also external sorting, merge sort, and sort-join algorithms.