# Multiway Merge Sort

# Multiway Merge Sort

Multiway merge sort generalizes merge sort by splitting the input into $k$ parts instead of two, and merging $k$ sorted sequences at each step.

It is especially useful when merging cost dominates, such as in external memory or database systems.

## Problem

Given an array $A$ of length $n$, reorder it such that:

$$
A[0] \le A[1] \le \dots \le A[n-1]
$$

## Idea

Instead of binary splitting:

$$
n \to \frac{n}{2} + \frac{n}{2}
$$

multiway merge sort splits into $k$ parts:

$$
n \to \frac{n}{k} + \dots + \frac{n}{k}
$$

Each part is sorted recursively, then merged using a $k$-way merge.

The merge step uses a priority queue or tournament tree to efficiently select the smallest element among the $k$ sequences.

## Algorithm

```text id="m3k8xp"
multiway_merge_sort(A, k):
    if length(A) <= 1:
        return A

    split A into k parts

    for each part:
        recursively sort part

    return k_way_merge(parts)
```

Merge step:

```text id="q7v2tn"
k_way_merge(parts):
    create min heap

    insert first element of each part into heap

    result = []

    while heap not empty:
        extract minimum element
        append to result

        if that part has more elements:
            insert next element into heap

    return result
```

## Example

Let:

$$
A = [9, 2, 7, 4, 6, 1, 8, 3, 5]
$$

Split into $k = 3$ parts:

* [9, 2, 7]
* [4, 6, 1]
* [8, 3, 5]

Sort each:

* [2, 7, 9]
* [1, 4, 6]
* [3, 5, 8]

Merge:

$$
[1,2,3,4,5,6,7,8,9]
$$

## Correctness

Each recursive call sorts its subarray. The $k$-way merge always extracts the smallest remaining element among all parts, ensuring that the result is sorted. By induction on the recursion depth, the final array is sorted.

## Complexity

| metric          | value         |
| --------------- | ------------- |
| recursion depth | $O(\log_k n)$ |
| merge cost      | $O(n \log k)$ |
| total time      | $O(n \log n)$ |

Space:

$$
O(n)
$$

## Properties

| property        | value    |
| --------------- | -------- |
| stable          | yes      |
| in-place        | no       |
| merge structure | k-way    |
| parallelism     | moderate |

## Notes

Multiway merge sort reduces recursion depth compared to binary merge sort, but increases merge complexity.

It is particularly effective in:

* external memory sorting
* database systems
* distributed systems

In these settings, reducing the number of merge passes can significantly improve performance.

## Implementation

```python id="k8s3xp"
import heapq

def multiway_merge_sort(a, k=2):
    if len(a) <= 1:
        return a

    size = len(a)
    parts = []
    step = (size + k - 1) // k

    for i in range(0, size, step):
        parts.append(multiway_merge_sort(a[i:i + step], k))

    return k_way_merge(parts)

def k_way_merge(parts):
    heap = []
    result = []

    for i, part in enumerate(parts):
        if part:
            heap.append((part[0], i, 0))

    heapq.heapify(heap)

    while heap:
        val, part_idx, elem_idx = heapq.heappop(heap)
        result.append(val)

        if elem_idx + 1 < len(parts[part_idx]):
            next_val = parts[part_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, part_idx, elem_idx + 1))

    return result
```