PHP 7 Data Structures and Algorithms

Implementing merge sort

We will first write the divide part followed by the merge or conquer part. PHP has some built-in functions to split an array. We will use the array_slice function to do the splitting. Here is the code to do this:

function mergeSort(array $arr): array {     $len = count($arr);     $mid = (int) $len / 2;     if ($len == 1)          return $arr;     $left  = mergeSort(array_slice($arr, 0, $mid));     $right = mergeSort(array_slice($arr, $mid));     return merge($left, $right); }

As we can see from the code, we split the array in a recursive way until the array size becomes 1. When array size is 1, we start to merge backward, just like the last image. Here is the code for the merge function, which will take two arrays, and merge them into one as ...