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$ or $B$ .

Core Idea

Funnel sort divides the input into many small pieces, sorts each piece recursively, then merges them using a special structure that preserves locality across all memory levels.

The key component is the $k$ -funnel, a recursive merging network that merges $k$ sorted sequences efficiently.

High-Level Algorithm

funnel_sort(A):
    if size(A) small:
        sort directly
        return

    partition A into k subarrays
    recursively funnel_sort each subarray

    merge k sorted subarrays using a k-funnel

Typically:

k = N^{1/3}

Each subproblem has size:

N^{2/3}

Funnel Structure

A $k$ -funnel merges $k$ sorted input streams into one output stream.

It consists of:

smaller funnels recursively arranged
internal buffers between stages
a hierarchy of merging nodes

k inputs
   -> small funnels
       -> intermediate buffers
           -> larger funnels
               -> output

The design ensures that data moves through buffers in blocks, which reduces cache misses.

Example (Conceptual)

Suppose we merge 8 sorted streams.

Instead of merging all 8 directly with a heap, funnel sort builds a tree:

merge pairs into 4 streams
merge those into 2 streams
merge final 2 into 1

Each merge is buffered and structured so that intermediate data fits into cache at some level of recursion.

Correctness

Each recursive call sorts its subarray correctly. The funnel merges sorted inputs by always selecting the smallest available element across inputs.

Since every input stream is sorted, and merging preserves order, the final output is sorted. The algorithm processes all elements exactly once in merging, so no element is lost or duplicated.

Complexity

Comparison Complexity

O(N \log N)

Cache Complexity

Funnel sort achieves optimal bound:

O\left(\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B}\right)

This matches the lower bound for comparison-based sorting in the cache model.

Why It Works

The funnel structure ensures:

data is accessed sequentially within buffers
recursive levels eventually fit in cache
each level reduces random memory access
no parameter tuning is required

Comparison with Merge Sort

property	merge sort	funnel sort
cache aware	partially	fully cache oblivious
merge structure	flat	recursive
cache complexity	suboptimal	optimal
implementation	simple	complex

When to Use

Funnel sort is mainly of theoretical and research interest. It demonstrates that optimal cache performance can be achieved without knowing hardware parameters.

In practice, simpler algorithms such as cache-aware merge sort or tuned multiway merge sort are often preferred due to lower constant factors and easier implementation.

Implementation Sketch

A full funnel implementation is complex. The following shows only the structure.

def funnel_sort(a):
    if len(a) <= 32:
        return sorted(a)

    k = int(len(a) ** (1/3))
    if k < 2:
        k = 2

    size = len(a) // k
    parts = [a[i:i+size] for i in range(0, len(a), size)]

    parts = [funnel_sort(p) for p in parts]

    return merge_all(parts)

def merge_all(parts):
    import heapq

    heap = []
    iters = [iter(p) for p in parts]

    for i, it in enumerate(iters):
        try:
            heapq.heappush(heap, (next(it), i))
        except StopIteration:
            pass

    result = []

    while heap:
        val, i = heapq.heappop(heap)
        result.append(val)
        try:
            heapq.heappush(heap, (next(iters[i]), i))
        except StopIteration:
            pass

    return result

Notes

Funnel sort separates correctness from memory efficiency. The merging rule is standard, but the funnel structure organizes data movement so that each level of memory hierarchy is used efficiently without explicit tuning.