Sorting beyond main memory: external merge sort, polyphase merge, cache-oblivious techniques, LSM compaction, and database sort phases.
| 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 |
External Merge SortSort data that does not fit in memory by dividing it into sorted runs and merging them using external storage.
TPMMSExternal sorting algorithm that performs run generation and a single multiway merge using limited memory.
Polyphase Merge SortExternal sorting algorithm that distributes sorted runs unevenly across files so repeated merges need fewer empty files and less redistribution.
Balanced K Way Merge SortExternal sorting algorithm that repeatedly merges groups of k sorted runs until one final sorted run remains.
Cascade Merge SortExternal sorting method that merges sorted runs through staged levels so output from one level feeds the next.
Distribution Sweeping SortExternal-memory sorting method that partitions data into key ranges, sorts each range, and concatenates the sorted partitions.
Cache Aware SortingSorting techniques that explicitly use knowledge of cache size and block size to minimize memory hierarchy cost.
Cache Oblivious SortingSorting techniques that achieve good cache behavior without explicitly knowing cache size or block size.
Funnel SortCache oblivious sorting algorithm that achieves optimal memory transfer complexity using recursive multiway merging structures called funnels.
Buffer Tree SortExternal-memory sorting method that inserts records into a buffered tree and extracts them in sorted order.
B Tree Bulk Load SortSorting method that builds a B-tree directly from sorted data using bulk loading to minimize I/O operations.
LSM Compaction SortSorting through hierarchical merging in Log Structured Merge Trees using compaction across levels.
Database External SortExternal sorting procedure used by database systems for ORDER BY, GROUP BY, DISTINCT, and sort-merge joins.
Sort Merge Join Sort PhaseThe sorting stage used before a sort-merge join when one or both inputs are not already ordered by the join key.
Replacement Selection Run GenerationExternal sorting technique that uses a heap to produce initial sorted runs longer than the available memory.
Tape Merge SortExternal sorting algorithm that distributes sorted runs across sequential storage tapes and repeatedly merges them.
Memory Mapped External SortExternal sorting method that uses memory-mapped files so large data can be accessed through virtual memory while still sorting in chunks and merging runs.
Chunked SortSorting method that divides input into bounded-size chunks, sorts each chunk independently, and then combines the chunks.
Spill SortSorting method that keeps data in memory until a memory limit is reached, then spills sorted runs to external storage and merges them.
Parallel External Merge SortExternal sorting algorithm that performs run generation and merging concurrently across multiple processors and disks.
External Radix SortExternal-memory radix sort that processes large datasets by distributing records into digit-based buckets across multiple passes.
External Sample SortExternal-memory sorting algorithm that uses sampling to partition data into balanced buckets, then sorts each bucket independently.
External Bucket SortExternal-memory bucket sort that partitions records into ordered buckets stored on disk and sorts each bucket separately.
Loser Tree MergeEfficient k-way merge using a tournament tree that stores losers to reduce comparisons and improve external merge performance.
Winner Tree MergeK-way merge using a tournament tree that stores winners at internal nodes and repeatedly updates the winning path.