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 :

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 :

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.