module Weihnacht where

import Data.List(sort,sortBy)
import System.Random
import IOExts

mergeSort :: Ord a => [a] -> [a]
mergeSort [ ] = [ ]
mergeSort [x] = [x]
mergeSort xs  = mergeSort a `merge` mergeSort b
  where (a,b) = pair xs
  	pair (x:x':xs) = let (a,a') = pair xs in (x:a, x':a')
	pair x = (x,[])
	merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys)
	                    | True   = y : merge (x:xs) ys
	merge x y = x ++ y


bubbleSort :: Ord a => [a] -> [a]
bubbleSort xs | xs == xs' = xs
              | otherwise = bubbleSort xs'
   where xs' = bubbleUp xs
         bubbleUp (x1:x2:xs) = min x1 x2 : bubbleUp (max x2 x1 : xs)
	 bubbleUp xs = xs


lossySort :: Ord a => [a] -> [a]
lossySort (x:y:xs) = [min x y, max y x]
lossySort xs = xs


isSort1 :: Ord a => [a] -> Bool
isSort1 (x1:x2:xs) | x1 <= x2  = isSort1 (x2:xs)
                   | otherwise = False
isSort1 _  = True


isSort2 :: Ord a => [a] -> Bool
isSort2 xs = sort xs == xs



isSort3 :: Ord a => [a] -> Bool
isSort3 xs@(x:xs') = all id $ zipWith (<=) xs xs'
isSort3 _          = True

isSort4 :: Ord a => [a] -> Bool
isSort4 xs = [ (xs !! i, xs !! j) |
               i <- [0     .. length xs - 2],
               j <- [i + 1 .. length xs - 1],
	       xs !! i > xs !! j
	     ] == []
		       
shuffle :: [a] -> [a]
shuffle = sortBy rand
  where rand x y = if fst . random $ unsafePerformIO newStdGen then LT else GT

randomSort :: Ord a => [a] -> [a]
randomSort = head . filter isSort . iterate shuffle

isSort :: Ord a => [a] -> Bool
isSort = isSort1