<?php
//merge sort example

function merge_sort($unsortedArray){

    $arrayCount = count($unsortedArray);

    //check if one element (passed by merge function or main function)
    if($arrayCount === 1){
        //already sorted
        return $unsortedArray;
    }

    //middle element
    $middle = (int)floor($arrayCount / 2) ;

    $arrayChunk = array_chunk($unsortedArray,$middle);

    //first half
    $firstHalf = $arrayChunk[0];

    //second half (combine two chunks if odd number of element is present)
    if($arrayCount % 2 == 1){
        $secondHalf = array_merge($arrayChunk[1],$arrayChunk[2]);
    }else{
        $secondHalf = $arrayChunk[1];
    }

    return merge(merge_sort($firstHalf),merge_sort($secondHalf));
}


function merge($firstHalf,$secondHalf){

    $resultArray = [];
    $firstHalfIndex = 0;
    $secondHalfIndex = 0;


    while ($firstHalfIndex < count($firstHalf) && $secondHalfIndex < count($secondHalf)) {
    // var_dump($firstHalf[$firstHalfIndex] < $secondHalf[$secondHalfIndex]);
        if ($firstHalf[$firstHalfIndex] < $secondHalf[$secondHalfIndex]) {
            array_push($resultArray,$firstHalf[$firstHalfIndex]);
        $firstHalfIndex++;
        } else {
            array_push($resultArray,$secondHalf[$secondHalfIndex]);
        $secondHalfIndex++;
        }

    }

    // var_dump($resultArray,array_slice($firstHalf,$firstHalfIndex),array_slice($resultArray,$secondHalfIndex));
    // die();
    if(!empty(array_slice($firstHalf,$firstHalfIndex))){
        $resultArray = array_merge($resultArray,array_slice($firstHalf,$firstHalfIndex));
    }

    // var_dump($resultArray);
    // die();

    if(!empty(array_slice($resultArray,$secondHalfIndex))){
        $resultArray = array_merge($resultArray,array_slice($secondHalf,$secondHalfIndex));
    };

    return $resultArray;
}


//unsorted array
$unsortedArray = [200,100,50,5000,2,3000,343,4323,121,23232323,200];
var_dump($unsortedArray);

$sortedArray =  merge_sort($unsortedArray);

var_dump($sortedArray)
?>