## Merge Sort in PHP

Merge sort Algorithm is based on divide and conquer method.It shows the worst case time complexity.

## Source code :

```<?php

\$unsorted_numbers = array(3,7,1,26,43,12,6,21,23,73);
function merge_arrays(\$left_arr, \$right_arr){
\$res = array();
while (count(\$left_arr) > 0 && count(\$right_arr) > 0){
if(\$left_arr[0] > \$right_arr[0]){
\$res[] = \$right_arr[0];
\$right_arr = array_slice(\$right_arr , 1);
}else{
\$res[] = \$left_arr[0];
\$left_arr = array_slice(\$left_arr, 1);
}
}
while (count(\$left_arr) > 0){
\$res[] = \$left_arr[0];
\$left_arr = array_slice(\$left_arr, 1);
}
while (count(\$right_arr) > 0){
\$res[] = \$right_arr[0];
\$right_arr = array_slice(\$right_arr, 1);
}
return \$res;
}

function mergesort(\$array)
{
if(count(\$array) == 1 ) return \$array;
\$mid = count(\$array) / 2;
\$left_arr = array_slice(\$array, 0, \$mid);
\$right_arr = array_slice(\$array, \$mid);
\$left_arr = mergesort(\$left_arr);
\$right_arr = mergesort(\$right_arr);
return merge_arrays(\$left_arr, \$right_arr);
}

\$sorted_numbers = mergesort(\$unsorted_numbers);

print_r(\$sorted_numbers);```

```Array
(
[0] => 1
[1] => 3
[2] => 6
[3] => 7
[4] => 12
[5] => 21
[6] => 23
[7] => 26
[8] => 43
[9] => 73
)```

## Algorithm :

1. Divide the array into equal halves.
2. Combine them in a sorted manner.