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.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
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
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics