Skip to content

Instantly share code, notes, and snippets.

@rwbogl
Last active Sep 10, 2018
Embed
What would you like to do?
Basic profiling of quicksort and mergesort in Haskell
import Data.List
mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
where size = div (length l) 2
(left, right) = splitAt size l
merge :: Ord a => [a] -> [a] -> [a]
merge ls [] = ls
merge [] vs = vs
merge first@(l:ls) second@(v:vs)
| l < v = l : merge ls second
| otherwise = v : merge first vs
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
where pivotIndex = div (length l) 2
pivot = l !! pivotIndex
[less, greater] = foldl addElem [[], []] $ enumerate l
addElem [less, greater] (index, elem)
| index == pivotIndex = [less, greater]
| elem < pivot = [elem:less, greater]
| otherwise = [less, elem:greater]
enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]
isSorted :: Ord a => [a] -> Bool
isSorted l = and $ zipWith (<=) l (tail l)
testSize = 20
testList = [(1299709 * 144737 - 10) `mod` x | x <- [1..2^testSize]]
main = do
print $ isSorted $ mergesort [1..2^testSize]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment