﻿ PHP: Sort a list of elements using Merge sort - 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 :

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.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.

﻿