クイックソート VS マージソート

今日は、軽い実験。Haskellの練習がてら、quick sortとmerge sortを比較する。

まず、quick sort。

-- quick sort
qsort :: (Ord a) => [a] -> [a]
qsort []     = []
qsort (x:xs) = let left  = filter (<x) xs
                   right = filter (>=x) xs
               in qsort left ++ [x] ++ qsort right

Haskellは美しい。次に、merge sort。

msort :: (Ord a) => [a] -> [a]
msort [x] = [x]
msort [x, y] = [min x y, max x y]
msort xs = let len = length xs `div` 2
               pre = msort $ take len xs
               suf = msort $ drop len xs
           in merge pre suf

merge [] [] = []
merge x []  = x
merge [] y  = y
merge (x:xs) (y:ys)
     | x <= y    = x : merge xs (y:ys)
     | otherwise = y : merge (x:xs) ys

もうちょっと綺麗に書けそうだが、こんなもんだろう。

適当に乱数をソートしてみる。

getRandoms :: Int -> [Int]
getRandoms n = take n $ randomRs (1, 100000) $ mkStdGen 0

n=100,000で比較。

quick sort 0.653[s]

merge sort 0.891[s]

quick sortの弱点を突いてみる。ソート済みのリストを入力として与えてみる。[1..100000]で比較。

quick sort 815.877[s]

marge sort 0.465[s]

quick sortはpivot選択すれば改良はできるけど、それでも理論上の最悪計算量はO(n^2)。merge sortは常に平衡二分木を形成するように分割するので、計算量は常にO(n log n)。ランダムなデータに対してはquick sortが速い場合が多いようだが、実用上はmerge sortを使用した方が安心な気がする。