合併兩個已排序陣列：PHP、Python、C、Go 多語言演算法實作比較

問題描述

給定兩個已遞增排序的陣列，將其合併為一個新的有序陣列。這是經典的「合併排序」核心步驟，也是常見面試題。關鍵在於利用「已排序」特性，以 O(m+n) 時間複雜度完成，避免重新排序的 O((m+n) log(m+n))。

核心演算法邏輯

1. 雙指標分別指向兩陣列起始位置
2. 比較兩指標元素，較小者放入結果陣列，該指標前進
3. 重複直到其中一陣列耗盡
4. 將剩餘陣列所有元素直接接在結果後方（因已排序且必大於已合併元素）

多語言實作對照

PHP 版（使用 array_shift 為教學示範，實務建議用索引）

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

    while ($i < $lenA && $j < $lenB) {
        if ($a[$i] <= $b[$j]) {
            $result[] = $a[$i++];
        } else {
            $result[] = $b[$j++];
        }
    }
    // 附加剩餘元素
    while ($i < $lenA) $result[] = $a[$i++];
    while ($j < $lenB) $result[] = $b[$j++];

    return $result;
}

// 測試
$a = [1, 2, 3, 4, 5, 6];
$b = [2, 3, 4, 10, 10, 10, 10];
print_r(mergeSortedArrays($a, $b));
/* 結果：
Array (
    [0] => 1 [1] => 2 [2] => 2 [3] => 3 [4] => 3 [5] => 4
    [6] => 4 [7] => 5 [8] => 6 [9] => 10 [10] => 10 [11] => 10 [12] => 10
) */

Python 版（列表推導式風格）

def merge_sorted(a, b):
    i = j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

print(merge_sorted([1,2,3,4,5,6], [2,3,4,10,10,10,10]))

C 版（指標操作，高效能）

#include 
#include 

int* merge_sorted(const int* a, int len_a, const int* b, int len_b, int* out_len) {
    int* result = malloc((len_a + len_b) * sizeof(int));
    int i = 0, j = 0, k = 0;

    while (i < len_a && j < len_b) {
        result[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
    }
    while (i < len_a) result[k++] = a[i++];
    while (j < len_b) result[k++] = b[j++];

    *out_len = k;
    return result;
}

int main() {
    int a[] = {1,2,3,4,5,6};
    int b[] = {2,3,4,10,10,10,10};
    int len;
    int* c = merge_sorted(a, 6, b, 7, &len);
    for (int i = 0; i < len; i++) printf("%d ", c[i]);
    free(c);
    return 0;
}

Go 版（切片操作，簡潔）

package main
import "fmt"

func mergeSorted(a, b []int) []int {
    result := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) && j < len(b) {
        if a[i] <= b[j] {
            result = append(result, a[i]); i++
        } else {
            result = append(result, b[j]); j++
        }
    }
    result = append(result, a[i:]...)
    result = append(result, b[j:]...)
    return result
}

func main() {
    a := []int{1,2,3,4,5,6}
    b := []int{2,3,4,10,10,10,10}
    fmt.Println(mergeSorted(a, b))
}

效能分析與優化建議

PHP 實務優化版（生產環境建議）

function mergeSortedOptimized(array $a, array $b): array {
    $result = [];
    $resultCount = 0;
    $i = $j = 0;
    $lenA = count($a);
    $lenB = count($b);

    // 預分配記憶體（PHP 7.1+）
    $result = array_pad([], $lenA + $lenB, null);

    while ($i < $lenA && $j < $lenB) {
        $result[$resultCount++] = ($a[$i] <= $b[$j]) ? $a[$i++] : $b[$j++];
    }
    while ($i < $lenA) $result[$resultCount++] = $a[$i++];
    while ($j < $lenB) $result[$resultCount++] = $b[$j++];

    return $result; // 已為連續索引陣列
}

延伸應用

• 外部排序：大檔案分塊排序後，多路歸併
• 資料庫 Merge Join：已排序資料集連接
• 日誌合併：多來源時間序列日誌統一排序