CODEWITHSUNDEEP
sortinghaskellmergesort
Mostafa Ibrahim
Mostafa Ibrahim

Reputation: 61

Haskell merge sort implementation

I am trying to solve this question: De fine a recursive function msort :: Ord a => [a] -> [a] that imple- ments merge sort, which can be specified by the following two rules:  Lists of length 1 are already sorted;  Other lists can be sorted by sorting the two halves and merging the resulting lists.

But I am having a hard time understanding how exactly the code of merge sort work.

here is my code ::

merge :: Ord a => [a] -> [a] -> [a]
merge [] [] = []
merge (x:xs) (y:ys) | y > x =  (x:xs) ++  (y:ys)
                    |otherwise =  (y:ys) ++  (x:xs)


msort :: Ord a => [a] -> [a]
--base case , if length less than or equal 1 , then list is already  sorted
msort [] = [] -- how to implement base case?
msort (x:xs)  = merge  (take (length(x:xs) `div` 2 ) (x:xs)) (drop (length(x:xs) `div` 2 ) (x:xs))

Upvotes: 0

Views: 3040

Answers (2)

dfeuer
dfeuer

Reputation: 48591

Because I can't resist a challenge, here's an efficient, incremental, stable top-down mergesort. The same design with a couple minor tweaks should produce an efficient (but non-incremental) mergesort for a strict language; laziness is only used in the merge function, so it should be possible to do some juggling to avoid it if desired.

{-# language BangPatterns #-}

import Control.Monad

-- Divide a list into the first n `quot` 2 elements and
-- the rest. The front of the list is reversed.
half :: [a] -> ([a], [a])
half = join (go []) where
  go front ts [] = (front, ts)
  go front ts [_] = (front, ts)
  go front (t:ts) (_:_:hs) = go (t:front) ts hs

-- Some care is required to make the sort stable.
merge :: Ord a => Bool -> [a] -> [a] -> [a]
merge _ [] ys = ys
merge _ xs [] = xs
merge up xxs@(x : xs) yys@(y : ys)
  | (if up then (<=) else (<)) x y = x : merge up xs yys
  | otherwise = y : merge up xxs ys

msort :: Ord a => [a] -> [a]
msort = go True where
  go _ [] = []
  go _ xs@[_] = xs
  go !up xs = merge up frontSorted rearSorted where
    frontSorted = go (not up) front
    rearSorted = go up rear
    (front, rear) = half xs

A version that uses laziness more heavily is considerably easier to write and understand, but may be susceptible to a subtle space leak if care is not taken to control certain compiler optimizations:

-- Split a list in half, with both halves in order
half :: [a] -> ([a], [a])
half = join go
  where
    go t [] = ([], t)
    go t [_] = ([], t)
    go (t : ts) (_:_:hs) = (t : front, rear)
      where (front, rear) = go ts hs -- Interesting laziness

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge xxs@(x:xs) yys@(y:ys)
  | x <= y    = x : merge xs yys
  | otherwise = y : merge xxs ys

msort :: Ord a => [a] -> [a]
msort []  = []
msort [x] = [x]
msort xs  = merge (msort front) (msort rear)
  where (front, rear) = half xs

For completeness, I should mention that bottom-up mergesort seems rather more natural in Haskell.

Upvotes: 1

aplainzetakind
aplainzetakind

Reputation: 500

Your merge function has two issues.

i) Patterns are not exhaustive: If precisely one of the lists is empty, there's no match. You should have

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = something

ii) Your something is not actually merge sorting, it is looking at the heads and concatenates the two lists based on the comparison of the heads. For instance, if given [1,4,5] and [2,3,4], 1 would be bound to x, 2 to y, and then since y > x holds, then it would return [1,4,5,2,3,4], clearly unsorted, though the two given lists were sorted.

Imagine the merging as follows. Given two lists, you see only the heads, and pick the smaller one. In place of the one you removed, the next element rolls in, and you keep doing the same thing. This is a recursive process; after each pick, you do the same thing. In code:

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

As for the actual sorting :: Ord a => [a] -> [a], you must also work with halves that are already sorted, which also calls for recursion:

msort :: Ord a => [a] -> [a]
msort []  = []
msort [x] = [x]
msort xs  = merge firstHalfSorted secondHalfSorted
     where firstHalfSorted  = msort . fst $ halves
           secondHalfSorted = msort . snd $ halves
           halves           = splitAt halfPoint xs
           halfPoint        = length xs `div` 2

Upvotes: 4

Related Questions