PHP Searching and Sorting Algorithm: Merge sort

Last update on June 03 2025 12:57:38 (UTC/GMT +8 hours)

Write a PHP program to sort a list of elements using Merge sort.

According to Wikipedia "Merge sort (also commonly spelled mergesort) is an O (n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output."

Pictorial presentation - Merge search algorithm :

PHP : merge sort

Sample Solution :

PHP Code :

<?php
// Function to perform merge sort on an array
function merge_sort($my_array){
    // Base case: if the array has only one element, return it
    if(count($my_array) == 1 ) return $my_array;
    
    // Calculate the middle index of the array
    $mid = count($my_array) / 2;
    
    // Divide the array into two halves: left and right
    $left = array_slice($my_array, 0, $mid);
    $right = array_slice($my_array, $mid);
    
    // Recursively call merge_sort on each half
    $left = merge_sort($left);
    $right = merge_sort($right);
    
    // Merge the sorted halves
    return merge($left, $right);
}

// Function to merge two sorted arrays
function merge($left, $right){
    $res = array(); // Initialize an empty array to store the merged result
    
    // Compare elements from left and right arrays and merge them in sorted order
    while (count($left) > 0 && count($right) > 0){
        if($left[0] > $right[0]){
            $res[] = $right[0];
            $right = array_slice($right , 1);
        }else{
            $res[] = $left[0];
            $left = array_slice($left, 1);
        }
    }
    
    // If any elements are remaining in the left array, append them to the result
    while (count($left) > 0){
        $res[] = $left[0];
        $left = array_slice($left, 1);
    }
    
    // If any elements are remaining in the right array, append them to the result
    while (count($right) > 0){
        $res[] = $right[0];
        $right = array_slice($right, 1);
    }
    
    // Return the merged result
    return $res;
}

// Example usage:
$test_array = array(100, 54, 7, 2, 5, 4, 1); // Define an array
echo "Original Array : ";
echo implode(', ',$test_array ); // Print the original array
echo "\nSorted Array :"; 
echo implode(', ',merge_sort($test_array))."\n"; // Sort the array using merge sort and print the sorted array
?>

Output:

Original Array : 100, 54, 7, 2, 5, 4, 1                             
Sorted Array : 1, 2, 4, 5, 7, 54, 100

Explanation:

In the exercise above,

merge_sort($my_array): This function implements the merge sort algorithm recursively. It divides the input array into two halves, recursively sorts each half, and then merges them back together in sorted order.
merge($left, $right): This function merges two sorted arrays ('$left' and '$right') into a single sorted array. It compares elements from both arrays and selects the smallest element to add to the result array. This is done until one of the arrays is empty.
Finally, the code defines an example array '$test_array', prints the original array, calls "merge_sort()" to sort the array, and then prints the sorted array.

Flowchart :

Go to:

PREV : Write a PHP program to sort a list of elements using Patience sort.
NEXT : PHP Challenges Exercises Home.

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.