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.).
$result = array_slice($arr1,1,5); sort($result); echo implode(' ', $result);
? – CᴴᵁᴮᴮʸNᴵᴺᴶᴬ Oct 10 at 16:25