sorted merge

Combining two or more already sorted sequences into one sorted sequence by repeatedly taking the smallest front item.

In more detail

Merging two lists of total length n takes O(n) time. It is the combine step of merge sort and, generalised to k inputs with a heap, the core of external sorting. Taking from the left input on ties keeps the merge stable.

Related terms

Taught in

References