tag

#replacement-selection

2 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

External Replacement Selection

External Replacement Selection External replacement selection is the disk-oriented version of replacement selection. It generates long sorted runs from data that does not fit in memory, forming the first phase of external merge sort. You use it when sorting large datasets stored on disk. Problem Given a dataset too large to fit into memory and a memory buffer of size ( M ), generate sorted runs on disk such that:...

Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Replacement Selection

Replacement Selection Replacement selection is a run generation technique used in external sorting. It produces sorted runs that are often longer than the available memory size by using a priority queue. You use it when sorting data that does not fit in memory. Problem Given a stream of elements and limited memory of size ( M ), produce sorted runs on disk such that: each run is sorted runs are...