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);

Output :

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.

Output :


                

Comments :