10. External Memory, Cache, and Database Sorting

Sorting beyond main memory: external merge sort, polyphase merge, cache-oblivious techniques, LSM compaction, and database sort phases.

25 items

10. External memory, cache, and database sorting, 25

index slug name
286 external-merge-sort External Merge Sort
287 two-phase-multiway-merge-sort Two Phase Multiway Merge Sort
288 polyphase-merge-sort Polyphase Merge Sort
289 balanced-k-way-merge-sort Balanced K Way Merge Sort
290 cascade-merge-sort Cascade Merge Sort
291 distribution-sweeping-sort Distribution Sweeping Sort
292 cache-aware-sorting Cache Aware Sorting
293 cache-oblivious-sorting Cache Oblivious Sorting
294 funnel-sort Funnel Sort
295 buffer-tree-sort Buffer Tree Sort
296 b-tree-bulk-load-sort B Tree Bulk Load Sort
297 lsm-tree-compaction-sort LSM Tree Compaction Sort
298 database-external-sort Database External Sort
299 sort-merge-join-sort-phase Sort Merge Join Sort Phase
300 replacement-selection-run-generation Replacement Selection Run Generation
301 tape-merge-sort Tape Merge Sort
302 memory-mapped-external-sort Memory Mapped External Sort
303 chunked-sort Chunked Sort
304 spill-sort Spill Sort
305 parallel-external-merge-sort Parallel External Merge Sort
306 external-radix-sort External Radix Sort
307 external-sample-sort External Sample Sort
308 external-bucket-sort External Bucket Sort
309 k-way-loser-tree-merge K Way Loser Tree Merge
310 k-way-winner-tree-merge K Way Winner Tree Merge
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Merge Sort

Sort data that does not fit in memory by dividing it into sorted runs and merging them using external storage.
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

TPMMS

External sorting algorithm that performs run generation and a single multiway merge using limited memory.
algorithms sorting external-memory database
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Polyphase Merge Sort

External sorting algorithm that distributes sorted runs unevenly across files so repeated merges need fewer empty files and less redistribution.
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Balanced K Way Merge Sort

External sorting algorithm that repeatedly merges groups of k sorted runs until one final sorted run remains.
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Cascade Merge Sort

External sorting method that merges sorted runs through staged levels so output from one level feeds the next.
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Distribution Sweeping Sort

External-memory sorting method that partitions data into key ranges, sorts each range, and concatenates the sorted partitions.
algorithms sorting external-memory distribution-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Cache Aware Sorting

Sorting techniques that explicitly use knowledge of cache size and block size to minimize memory hierarchy cost.
algorithms sorting cache external-memory
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Cache Oblivious Sorting

Sorting techniques that achieve good cache behavior without explicitly knowing cache size or block size.
algorithms sorting cache external-memory
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Funnel Sort

Cache oblivious sorting algorithm that achieves optimal memory transfer complexity using recursive multiway merging structures called funnels.
algorithms sorting cache-oblivious external-memory
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Buffer Tree Sort

External-memory sorting method that inserts records into a buffered tree and extracts them in sorted order.
algorithms sorting external-memory buffer-tree
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

B Tree Bulk Load Sort

Sorting method that builds a B-tree directly from sorted data using bulk loading to minimize I/O operations.
algorithms sorting external-memory b-tree
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

LSM Compaction Sort

Sorting through hierarchical merging in Log Structured Merge Trees using compaction across levels.
algorithms sorting external-memory lsm-tree
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Database External Sort

External sorting procedure used by database systems for ORDER BY, GROUP BY, DISTINCT, and sort-merge joins.
algorithms sorting external-memory database
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Sort Merge Join Sort Phase

The sorting stage used before a sort-merge join when one or both inputs are not already ordered by the join key.
algorithms sorting external-memory database joins
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Replacement Selection Run Generation

External sorting technique that uses a heap to produce initial sorted runs longer than the available memory.
algorithms sorting external-memory heap
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Tape Merge Sort

External sorting algorithm that distributes sorted runs across sequential storage tapes and repeatedly merges them.
algorithms sorting external-memory merge-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Memory Mapped External Sort

External sorting method that uses memory-mapped files so large data can be accessed through virtual memory while still sorting in chunks and merging runs.
algorithms sorting external-memory memory-mapped-files
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Chunked Sort

Sorting method that divides input into bounded-size chunks, sorts each chunk independently, and then combines the chunks.
algorithms sorting external-memory chunking
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Spill Sort

Sorting method that keeps data in memory until a memory limit is reached, then spills sorted runs to external storage and merges them.
algorithms sorting external-memory database
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Parallel External Merge Sort

External sorting algorithm that performs run generation and merging concurrently across multiple processors and disks.
algorithms sorting external-memory parallel
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Radix Sort

External-memory radix sort that processes large datasets by distributing records into digit-based buckets across multiple passes.
algorithms sorting external-memory radix-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Sample Sort

External-memory sorting algorithm that uses sampling to partition data into balanced buckets, then sorts each bucket independently.
algorithms sorting external-memory sample-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

External Bucket Sort

External-memory bucket sort that partitions records into ordered buckets stored on disk and sorts each bucket separately.
algorithms sorting external-memory bucket-sort
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Loser Tree Merge

Efficient k-way merge using a tournament tree that stores losers to reduce comparisons and improve external merge performance.
algorithms sorting external-memory merge loser-tree
Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Winner Tree Merge

K-way merge using a tournament tree that stores winners at internal nodes and repeatedly updates the winning path.
algorithms sorting external-memory merge winner-tree