Skip to content

Instantly share code, notes, and snippets.

@b3k
Created August 1, 2013 13:40
Show Gist options
  • Save b3k/6131426 to your computer and use it in GitHub Desktop.
Save b3k/6131426 to your computer and use it in GitHub Desktop.
Multiple sort implementations in one class
<?php
class Sort {
public static function radix_sort($input) {
$min = min($input);
$max = max($input);
$temp = array_fill($min, $max - $min + 1, 0);
foreach ($input as $key => $val) {
$temp[$val]++;
}
$input = array();
foreach ($temp as $key => $val) {
if ($val == 1) {
$input[] = $key;
} else {
while ($val--) {
$input[] = $key;
}
}
}
return $input;
}
public static function merge_sort($arr) {
if (count($arr) <= 1) {
return $arr;
}
$left = array_slice($arr, 0, (int) (count($arr) / 2));
$right = array_slice($arr, (int) (count($arr) / 2));
$left = self::merge_sort($left);
$right = self::merge_sort($right);
$output = self::merge($left, $right);
return $output;
}
private static function merge($left, $right) {
$result = array();
while (count($left) > 0 && count($right) > 0) {
if ($left[0] <= $right[0]) {
array_push($result, array_shift($left));
} else {
array_push($result, array_shift($right));
}
}
array_splice($result, count($result), 0, $left);
array_splice($result, count($result), 0, $right);
return $result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment