PHP Program to Merge Two Sorted Arrays

You can merge two sorted arrays in PHP by comparing elements one by one and adding the smaller element to a new array using a loop; for example, use while loops with pointers to merge arrays like $merged = []; and then print the merged array.

Examples

Input[1, 3, 5], [2, 4, 6]

Output[1, 2, 3, 4, 5, 6]

Input[10, 20, 30], [15, 25, 35]

Output[10, 15, 20, 25, 30, 35]

Input[], [1, 2, 3]

Output[1, 2, 3]

How to Think About It

To merge two sorted arrays, start by looking at the first elements of both arrays. Compare them and pick the smaller one to add to a new array. Move forward in the array from which you took the element. Repeat this until you reach the end of one array, then add all remaining elements from the other array to the new array.

Algorithm

1

Start with two pointers at the beginning of each array.

2

Compare the elements at these pointers.

3

Add the smaller element to the merged array and move that pointer forward.

4

Repeat until one array is fully traversed.

5

Add all remaining elements from the other array to the merged array.

6

Return or print the merged array.

Code

php

<?php
function mergeSortedArrays($arr1, $arr2) {
    $i = 0; $j = 0; $merged = [];
    while ($i < count($arr1) && $j < count($arr2)) {
        if ($arr1[$i] < $arr2[$j]) {
            $merged[] = $arr1[$i];
            $i++;
        } else {
            $merged[] = $arr2[$j];
            $j++;
        }
    }
    while ($i < count($arr1)) {
        $merged[] = $arr1[$i];
        $i++;
    }
    while ($j < count($arr2)) {
        $merged[] = $arr2[$j];
        $j++;
    }
    return $merged;
}

$arr1 = [1, 3, 5];
$arr2 = [2, 4, 6];
$result = mergeSortedArrays($arr1, $arr2);
print_r($result);
?>

Output

Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
)

Dry Run

Let's trace merging [1, 3, 5] and [2, 4, 6] through the code

1

Initialize pointers and merged array

$i = 0, $j = 0, merged = []

2

Compare arr1[0]=1 and arr2[0]=2

1 < 2, add 1 to merged, increment i to 1

3

Compare arr1[1]=3 and arr2[0]=2

3 > 2, add 2 to merged, increment j to 1

4

Compare arr1[1]=3 and arr2[1]=4

3 < 4, add 3 to merged, increment i to 2

5

Compare arr1[2]=5 and arr2[1]=4

5 > 4, add 4 to merged, increment j to 2

6

Compare arr1[2]=5 and arr2[2]=6

5 < 6, add 5 to merged, increment i to 3

7

arr1 exhausted, add remaining arr2 elements

Add 6 to merged

i	j	merged
0	0	[]
1	0	[1]
1	1	[1, 2]
2	1	[1, 2, 3]
2	2	[1, 2, 3, 4]
3	2	[1, 2, 3, 4, 5]
3	3	[1, 2, 3, 4, 5, 6]

Why This Works

Step 1: Compare elements from both arrays

We look at the current elements from both arrays and pick the smaller one to keep the merged array sorted.

Step 2: Move pointer of chosen element

After adding the smaller element, we move the pointer forward in that array to check the next element.

Step 3: Add remaining elements after one array ends

When one array is fully added, we add all leftover elements from the other array because they are already sorted.

Alternative Approaches

Using array_merge and sort

php

<?php
$arr1 = [1, 3, 5];
$arr2 = [2, 4, 6];
$merged = array_merge($arr1, $arr2);
sort($merged);
print_r($merged);
?>

Simple but less efficient because it merges then sorts the whole array instead of merging sorted arrays directly.

Using SPL data structures (SplMinHeap)

php

<?php
$arr1 = [1, 3, 5];
$arr2 = [2, 4, 6];
$heap = new SplMinHeap();
foreach ($arr1 as $v) $heap->insert($v);
foreach ($arr2 as $v) $heap->insert($v);
$merged = [];
while (!$heap->isEmpty()) {
    $merged[] = $heap->extract();
}
print_r($merged);
?>

Uses a heap to merge but adds overhead; useful for merging many arrays or streams.

Complexity: O(n + m) time, O(n + m) space

Time Complexity

The program compares elements from both arrays once, so it runs in linear time relative to the total number of elements.

Space Complexity

It creates a new array to hold all elements, so space grows linearly with input size.

Which Approach is Fastest?

The two-pointer merge is fastest for sorted arrays because it avoids sorting the combined array, unlike array_merge + sort.

Approach	Time	Space	Best For
Two-pointer merge	O(n + m)	O(n + m)	Merging two sorted arrays efficiently
array_merge + sort	O((n + m) log(n + m))	O(n + m)	Quick code but less efficient
SplMinHeap	O((n + m) log(n + m))	O(n + m)	Merging multiple arrays or streams