PHP Program for Merge Sort with Example and Explanation

A PHP program for merge sort uses a mergeSort() function that splits the array into halves recursively and merges them in sorted order using a merge() helper function.

Examples

Input[5, 3, 8, 4, 2]

Output[2, 3, 4, 5, 8]

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

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

Input[]

Output[]

How to Think About It

To sort an array using merge sort, first split the array into two halves until each part has one or zero elements. Then, merge these small parts back together in order by comparing their elements one by one, building a sorted array step by step.

Algorithm

1

Check if the array length is 1 or less; if yes, return the array as it is already sorted.

2

Split the array into two halves.

3

Recursively apply merge sort on the left half.

4

Recursively apply merge sort on the right half.

5

Merge the two sorted halves into one sorted array.

6

Return the merged sorted array.

Code

php

<?php
function merge(array $left, array $right): array {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    return array_merge($result, $left, $right);
}

function mergeSort(array $arr): array {
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = intdiv(count($arr), 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);
    $left = mergeSort($left);
    $right = mergeSort($right);
    return merge($left, $right);
}

$input = [5, 3, 8, 4, 2];
$output = mergeSort($input);
print_r($output);

Output

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

Dry Run

Let's trace the array [5, 3, 8, 4, 2] through the merge sort code.

1

Split array

Split [5, 3, 8, 4, 2] into [5, 3] and [8, 4, 2]

2

Sort left half

Split [5, 3] into [5] and [3], then merge to [3, 5]

3

Sort right half

Split [8, 4, 2] into [8] and [4, 2], sort [4, 2] into [2, 4], then merge to [2, 4, 8]

4

Merge halves

Merge [3, 5] and [2, 4, 8] into [2, 3, 4, 5, 8]

Operation	Array State
Initial	[5, 3, 8, 4, 2]
Split	[5, 3] and [8, 4, 2]
Sort left half	[3, 5]
Sort right half	[2, 4, 8]
Merge halves	[2, 3, 4, 5, 8]

Why This Works

Step 1: Splitting the array

The code uses array_slice to split the array into two halves until each sub-array has one or zero elements, which are naturally sorted.

Step 2: Recursive sorting

The mergeSort function calls itself on each half, breaking down the problem into smaller sorting tasks.

Step 3: Merging sorted arrays

The merge function combines two sorted arrays by comparing their first elements and building a new sorted array.

Alternative Approaches

Iterative Merge Sort

php

<?php
function iterativeMergeSort(array $arr): array {
    $width = 1;
    $n = count($arr);
    while ($width < $n) {
        for ($i = 0; $i < $n; $i += 2 * $width) {
            $left = array_slice($arr, $i, $width);
            $right = array_slice($arr, $i + $width, $width);
            $merged = merge($left, $right);
            array_splice($arr, $i, count($merged), $merged);
        }
        $width *= 2;
    }
    return $arr;
}

function merge(array $left, array $right): array {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    return array_merge($result, $left, $right);
}

$input = [5, 3, 8, 4, 2];
$output = iterativeMergeSort($input);
print_r($output);

This method avoids recursion but is more complex to implement and less intuitive.

Using PHP built-in sort

php

<?php
$input = [5, 3, 8, 4, 2];
sort($input);
print_r($input);

Using PHP's built-in <code>sort()</code> is simpler and faster for most cases but does not teach the merge sort algorithm.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort divides the array into halves recursively (log n splits) and merges them back (n operations per merge), resulting in O(n log n) time.

Space Complexity

Merge sort requires extra space to hold temporary arrays during merging, so it uses O(n) additional memory.

Which Approach is Fastest?

Built-in PHP sort functions are fastest for practical use, but merge sort is useful for learning and stable sorting.

Approach	Time	Space	Best For
Recursive Merge Sort	O(n log n)	O(n)	Learning algorithm and stable sorting
Iterative Merge Sort	O(n log n)	O(n)	Avoiding recursion, complex implementation
PHP built-in sort()	O(n log n)	O(1)	Fastest and simplest for real applications