Haskell Practice - Merge Sort

老實說我也不太清楚是不是 Merge Sort ，只是照著感覺寫，而且感覺是效率不佳的 Merge Sort ... Orz，其中的 merge 是 scm 老師寫的，他寫了一封信，我很認真的看再很認真的忘掉再重寫中。

insertionSort [] = []
insertionSort (x:xs) = merge [x] (insertionSort xs)

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

測試結果如下:

*Main> mergeSort [3,1,5,2,6, -1, 10]
[-1,1,2,3,5,6,10]

---
想要改寫，不過應該是晚上的事了。

---

事情比想像中更糟，自己推一次，發現根本不是 Merge Sort 啊 ... Orz

---

上面那個應該是 insertion sort ... 緊急之間寫了下面這個 code 出來，但是會出錯 ... meeting 在即，等回來再說了 ...

mergeSort [] = []
mergeSort x = 
    if length x > 1 then 
        merge (mergeSort (fst (splitAt half x))) (mergeSort (snd (splitAt half x)))
    else x
    where half = truncate ( (fromIntegral (length x))/ (fromIntegral 2))

---

看起來是沒有出錯了，接下來該開始思考怎麼寫會比較好一點 XD。

---

2010/03/12 00:09 結果根本就在惡補怎麼操作 list ，發現自己是有看了，但是都忘完了 ... 到目前為止的版本

mergeSort (x:xs) 
    | xs == [] = [x]
    | otherwise = merge (mergeSort (take half (x:xs))) (mergeSort (drop half (x:xs)))
    where half = truncate ( (fromIntegral (length (x:xs)))/ (fromIntegral 2))

---

2009/03/12 10:19 AM 只是嘗試將 length 帶入 argument 中，實質上並無太大改變，我一直在想著長度的問題 ... 可是腦袋又是空掉了 ...

mergeSort [] = []
mergeSort x = mergeSort' x (length x) 

mergeSort' x l
    | l == 1 = x
    | otherwise = merge (mergeSort' (take half x) half) (mergeSort' (drop half x) (l-half))
    where half = truncate ((fromIntegral l)/(fromIntegral 2))

---

2009/03/14 11:38 pm 依 scm 在 comments 裡的建議把 uninterleave 寫出來，自己重寫 interleave ，發現有一點不太一樣(還好功能一樣 XD)

interleave [] ys = ys
interleave xs [] = xs
interleave (x:xs) (y:ys) = x:y:(interleave xs ys)
-- interleave (x:xs) (y:ys) = x:(interleave (y:ys) xs)

uninterleave :: [a] -> ([a],[a])
uninterleave [] = ([], [])
uninterleave (x:xs) = uninterleave' (x:xs) [] [] 

uninterleave':: [a] -> [a] -> [a] -> ([a], [a])
uninterleave' [] ys zs = (zs, ys)
uninterleave' (x:xs) ys zs = uninterleave' xs zs (x:ys)

mergeSort2 :: (Ord t) => [t] -> [t]
mergeSort2 [] = []
mergeSort2 (x:[])  = [x]
mergeSort2 xs = merge (mergeSort2 (fst (uninterleave xs))) (mergeSort2 (snd(uninterleave xs)))