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
- merge sort — A divide-and-conquer sort that splits the list in half, sorts each half recursively and then merges the two sorted halves.
- k-way merge — Merging k sorted sequences into one by keeping the current front item of each in a min-heap and repeatedly taking the smallest.
- stable sort — A sort that keeps items with equal keys in the same relative order they had before sorting.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Sorting In Real Systems: Stability, Keys And External Sort — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers