w3resource

PHP Searching and Sorting Algorithm: Merge sort

PHP Searching and Sorting Algorithm: Exercise-17 with Solution

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 :

Flowchart: PHP - program of Merge sort

PHP Code Editor:


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

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

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/php-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-17.php