The Big Programming Thread - Page 592

sort []  = []
sort [x] = [x]
sort l   = merge (sort $ take halfLength l) (sort $ drop halfLength l)
  where halfLength = length l `div` 2

merge a1 [] = a1
merge [] a2 = a2
merge (x:a1) (y:a2)
  | x >= y = y:(merge (x:a1)  a2   )
  | x < y  = x:(merge  a1    (y:a2))

sort [] = []
sort [x] = [x]
sort l = merge (sort a) (sort b)
  where (a,b) = splitAt (length l `div` 2) l

sort [] = []
sort [x] = [x]
sort l = merge (sort a) (sort b)
  where (a,b) = splitAt (length l `div` 2) l

$arr = [ 8, 0, 7, 2, 1, 3, 5, 9, 6, 4 ];

sort($arr);

print_r($arr);

/* output */
Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 4
    [5] => 5
    [6] => 6
    [7] => 7
    [8] => 8
    [9] => 9
)

/* props to Tobias Baldauf for this */

$data = [ 8, 0, 7, 2, 1, 3, 5, 9, 6, 4 ];

function mergesort($data) {
	if (count($data) > 1) {
		$data_middle = round(count($data)/2, 0, PHP_ROUND_HALF_DOWN);

		$data_left = mergesort(array_slice($data, 0, $data_middle));
		$data_right = mergesort(array_slice($data, $data_middle, count($data)));
		
		$counter_left = $counter_right = 0;
		
		 for ($i = 0; $i < count($data); ++$i) {
			if($counter_left === count($data_left)) {
				$data[$i] = $data_right[$counter_right];
				
				++$counter_right;
			} elseif (($counter_right === count($data_right)) || ($data_left[$counter_left] < $data_right[$counter_right])) {
				$data[$i] = $data_left[$counter_left];
				
				++$counter_left;
			} else {
				$data[$i] = $data_right[$counter_right];
				
				++$counter_right;
			}
		}
	}
	
	return $data;
}

$data = mergesort($data);

print_r($data);

fun mergesort [] = []
|   mergesort [x] = [x]
|   mergesort lst = 
    let fun merge ([],ys) = ys (*merges two sorted lists to form a sorted list *)
        |   merge (xs,[]) = xs
        |   merge (x::xs,y::ys) = 
              if x<y then
                x::merge (xs,y::ys)
              else
                y::merge (x::xs,ys)
        ; 
        val half = length(lst) div 2;
     in
        merge (mergesort (List.take (lst, half)),mergesort (List.drop (lst, half)))
     end
;