# 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$ 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

```text id="u9f2kq"
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

```text id="9u3mbc"
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.

```python id="k3q7va"
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)
```

```python id="h2d8pz"
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.