PHP 合併兩個有序陣列：雙指針歸併算法 O(n+m) 完整實現

給定兩個已排序的陣列，合併為一個新的有序陣列，不允許使用 sort() 等內建排序函數。這是經典的「歸併排序」合併步驟，時間複雜度 O(n+m)，空間複雜度 O(n+m)。本文提供標準雙指針實現與進階變體。

題目示例

$la = [3, 5, 8, 11];
$lb = [2, 6, 8, 9, 11, 15];
// 合併結果
$lc = [2, 3, 5, 6, 8, 8, 9, 11, 11, 15];

核心算法：雙指針歸併

<?php
function mergeSortedArrays(array $a, array $b): array {
    $i = $j = 0;
    $lenA = count($a);
    $lenB = count($b);
    $result = [];

    // 1. 同時遍歷，誰小取誰
    while ($i < $lenA && $j < $lenB) {
        if ($a[$i] <= $b[$j]) {
            $result[] = $a[$i++];
        } else {
            $result[] = $b[$j++];
        }
    }
    // 2. 收集剩餘尾部
    while ($i < $lenA) $result[] = $a[$i++];
    while ($j < $lenB) $result[] = $b[$j++];

    return $result;
}

$la = [3, 5, 8, 11];
$lb = [2, 6, 8, 9, 11, 15];
print_r(mergeSortedArrays($la, $lb));

輸出：

Array
(
    [0] => 2
    [1] => 3
    [2] => 5
    [3] => 6
    [4] => 8
    [5] => 8
    [6] => 9
    [7] => 11
    [8] => 11
    [9] => 15
)

面向對象封裝版（符合原文風格）

class UnionMerge {
    public function merge(array $listA, array $listB): array {
        $i = $j = 0;
        $lenA = count($listA);
        $lenB = count($listB);
        $merged = [];

        while ($i < $lenA && $j < $lenB) {
            $valA = $listA[$i];
            $valB = $listB[$j];
            if ($valA <= $valB) {
                $merged[] = $valA;
                $i++;
            } else {
                $merged[] = $valB;
                $j++;
            }
        }
        while ($i < $lenA) $merged[] = $listA[$i++];
        while ($j < $lenB) $merged[] = $listB[$j++];
        return $merged;
    }
}

$merger = new UnionMerge();
print_r($merger->merge([3,5,8,11], [2,6,8,9,11,15]));

進階變體

1. 去重合併（輸出唯一值）

function mergeUnique(array $a, array $b): array {
    $i = $j = 0;
    $result = [];
    $last = null;
    while ($i < count($a) && $j < count($b)) {
        $val = ($a[$i] <= $b[$j]) ? $a[$i++] : $b[$j++];
        if ($val !== $last) { $result[] = $val; $last = $val; }
    }
    while ($i < count($a)) { $val = $a[$i++]; if ($val !== $last) { $result[] = $val; $last = $val; } }
    while ($j < count($b)) { $val = $b[$j++]; if ($val !== $last) { $result[] = $val; $last = $val; } }
    return $result;
}
// [2,3,5,6,8,9,11,15]

2. 就地合併（$a 有足夠空間容納 $b，從後向前填充，O(1) 額外空間）

function mergeInPlace(array &$a, int $m, array $b, int $n): void {
    $i = $m - 1; $j = $n - 1; $k = $m + $n - 1;
    while ($i >= 0 && $j >= 0) {
        $a[$k--] = ($a[$i] > $b[$j]) ? $a[$i--] : $b[$j--];
    }
    while ($j >= 0) $a[$k--] = $b[$j--];
}
// 使用：$a = [3,5,8,11,0,0,0,0,0,0]; $b = [2,6,8,9,11,15];
// mergeInPlace($a, 4, $b, 6); // $a 變為合併結果

3. Generator 惰性合併（超大陣列/流式處理，記憶體 O(1)）

function mergeLazy(iterable $a, iterable $b): Generator {
    $itA = $a instanceof Traversable ? $a : new ArrayIterator($a);
    $itB = $b instanceof Traversable ? $b : new ArrayIterator($b);
    $itA->rewind(); $itB->rewind();
    $validA = $itA->valid(); $validB = $itB->valid();
    $valA = $validA ? $itA->current() : null;
    $valB = $validB ? $itB->current() : null;

    while ($validA && $validB) {
        if ($valA <= $valB) {
            yield $valA;
            $itA->next();
            $validA = $itA->valid();
            $valA = $validA ? $itA->current() : null;
        } else {
            yield $valB;
            $itB->next();
            $validB = $itB->valid();
            $valB = $validB ? $itB->current() : null;
        }
    }
    while ($validA) { yield $valA; $itA->next(); $validA = $itA->valid(); $valA = $validA ? $itA->current() : null; }
    while ($validB) { yield $valB; $itB->next(); $validB = $itB->valid(); $valB = $validB ? $itB->current() : null; }
}

foreach (mergeLazy([3,5,8,11], [2,6,8,9,11,15]) as $v) {
    echo $v . ' ';
}

效能對比（百萬級元素）

總結

合併兩個有序陣列是「雙指針」技巧的教科書級應用。關鍵要點：

1. 利用已有序特性，單次掃描完成，O(n+m) 最優。
2. 邊界處理：一方耗盡後，直接拼接另一方剩餘部分。
3. 根據場景選擇：普通 → 返回新陣列；內存敏感 → 就地合併或 Generator；需去重 → 增加 $last 變量。

掌握此模板，即可輕鬆應對「合併 K 個有序陣列」（小頂堆優化）、「求兩個有序陣列中位數」等進階面試題。