Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this small program in PHP implementing merge sort. I used one rather simple run time optimisation via using one additional array which allows faster merge operations:

function merge_impl(&$source,
                    &$target,
                    $source_offset,
                    $target_offset,
                    $left_run_length,
                    $right_run_length) {
    $target_index = $target_offset;
    $left = $source_offset;
    $left_bound = $left + $left_run_length;
    $right = $left_bound;
    $right_bound = $right + $right_run_length;

    while ($left != $left_bound and $right != $right_bound) {
        $target[$target_index++] =
                $source[$right] < $source[$left] ?
                $source[$right++] :
                $source[$left++];
    }

    while ($left != $left_bound) {
        $target[$target_index++] = $source[$left++];
    }

    while ($right != $right_bound) {
        $target[$target_index++] = $source[$right++];
    }
}

function mergesort_impl(&$source,
                        &$target,
                        $source_offset,
                        $target_offset,
                        $range_length) {
    if ($range_length < 2) {
        return;
    }

    $middle = intval($range_length / 2);

    mergesort_impl($target,
                   $source,
                   $target_offset,
                   $source_offset,
                   $middle);

    mergesort_impl($target,
                   $source,
                   $target_offset + $middle,
                   $source_offset + $middle,
                   $range_length - $middle);

    merge_impl($source,
               $target,
               $source_offset,
               $target_offset,
               $middle,
               $range_length - $middle);
}

function mergesort_ex(&$arr, $from_index, $to_index) {
    $range_length = $to_index - $from_index;
    if ($range_length < 2) {
        return;
    }

    $aux = array_merge(array(), 
                       array_slice($arr, 
                                   $from_index, 
                                   $range_length));
    mergesort_impl($aux, $arr, 0, $from_index, $range_length);
}

function mergesort(&$arr) {
    mergesort_ex($arr, 0, count($arr));
}

$arr1 = array(23, 20, 4, -1, 5, 43, 22);
echo "The entire array is: ";

for ($i = 0; $i < count($arr1); ++$i) {
    echo $arr1[$i] . " ";
}

echo "<br>";

mergesort_ex($arr1, 1, 6);

echo "Sorted array slice A[1, 6]: ";

for ($i = 1; $i < 6; ++$i) {
    echo "$arr1[$i] ";
}

As I have almost no experience with PHP, please tell me anything that comes to mind (API, naming/coding conventions, etc.).

share|improve this question
    
can you provide an implementation and/or explanation? – pppp Oct 10 at 15:04
    
@pppp The idea above is to use two arrays: one source array and one target array. At all recursion levels I merge the runs residing in the source array into a single merged run in the target array. The topmost call is such that the entire sorted range ends up in the array that was passed to the sort routine. This arrangement allows me to strip some unnecessary computation from the merging operation. – coderodde Oct 10 at 15:08
    
I may be missing the point of this function, but doesn't this basically replicate $result = array_slice($arr1,1,5); sort($result); echo implode(' ', $result); ? – CᴴᵁᴮᴮʸNᴵᴺᴶᴬ Oct 10 at 16:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.