tag

#cache-oblivious

3 pages tagged

Wiki › Algorithms › 01. Searching and Sorting › 10. External Memory, Cache, and Database Sorting ›

Funnel Sort

Funnel Sort Funnel sort is a cache oblivious sorting algorithm that achieves optimal cache complexity without knowing cache size or block size. It relies on a recursive multiway merge structure called a funnel . The algorithm matches the lower bound for comparison sorting in the external memory model. Model Assume: $N$ elements block size $B$ cache size $M$ tall cache condition $M = \Omega(B^2)$ The algorithm does not know $M$...
algorithms sorting cache-oblivious external-memory
Wiki › Algorithms › 01. Searching and Sorting › 12. Specialized Search and Sorted-Order Procedures ›

Van Emde Boas Layout Search

Van Emde Boas Layout Search Van Emde Boas layout search stores a binary search tree in recursive memory order. The layout is cache oblivious, which means it does not need to know the cache line size or memory block size in advance. The main idea is to split the tree into a top subtree and several bottom subtrees, then store each part recursively. Nodes that are close in the search...
algorithms searching binary-search cache-oblivious van-emde-boas-layout
Wiki › Algorithms › 01. Searching and Sorting › 7. Divide and Conquer Sorting ›

Cache Oblivious Merge Sort

Cache Oblivious Merge Sort Cache oblivious merge sort is a merge sort variant designed for memory hierarchies. It improves locality without knowing the cache size, block size, or number of cache levels. The algorithm uses recursive structure to make subproblems eventually fit into cache automatically. Problem Given an array $A$ of length $n$, reorder it such that: $$ A[0] \le A[1] \le \dots \le A[n-1] $$ while reducing cache misses...
algorithms sorting merge-sort cache-oblivious