CODEWITHSUNDEEP
listsortinghaskell
Mike Noel Higgs
Mike Noel Higgs

Reputation: 67

Ordering an Ordered list Function in Haskell

for my coursework I have to take two lists of numbers, sort them and then combine them and output the new list in order, this works if the lists are already in order as they are typed but not if say a 9 is at the start of a first list so the trouble I'm having is sorting the list after it's combined, in other languages I'd do this with a for loop, but not sure in Haskell here the code I have: 

merge :: Ord a => [a] -> [a] -> [a]
merge x [] = x
merge [] x = x
merge (x:xs) (y:ys) = if x < y
                          then x:(merge xs (y:ys))
                          else y:(merge (x:xs) ys)

Upvotes: 1

Views: 1414

Answers (3)

that other guy
that other guy

Reputation: 123410

It sounds like what you're actually supposed to implement is merge sort.

In merge sort you merge two sorted list to get one sorted list, yes. The missing observation is that a list of size 0 or 1 is necessarily already sorted.

This means that if you start applying your function to lists that are of size 0 or 1, then merge the results of that merge, then merge the result of that, eventually you will end up with a fully sorted list.

Here's an example:

-- Your function
merge :: Ord a => [a] -> [a] -> [a]
merge x [] = x
merge [] x = x
merge (x:xs) (y:ys) = if x < y
                          then x:(merge xs (y:ys))
                          else y:(merge (x:xs) ys)


-- Arbitrarily split a list into two ~equally sized smaller lists.
-- e.g. [2,7,1,8,2] -> ([2,7,1], [8,2])
split list = splitAt ((length list) `div` 2) list

-- Split a list into halves until each piece is size 0 or 1,
-- then 'merge' them back together.
mergeSort [] = []
mergeSort [x] = [x]
mergeSort list =
    let (firstHalf, secondHalf) = split list
    in merge (mergeSort firstHalf) (mergeSort secondHalf)

mergeSort [2,7,1,8,2] will evaluate to [1,2,2,7,8]. Using only your merge function, the list has been sorted.

Upvotes: 3

Davislor
Davislor

Reputation: 15134

For a problem like merge sort, you want to divide-and-conquer so that your input lists are always ordered. One way to do this by breaking the input down into singletons, which are always ordered by definition, then making your merge function tail-recursively insert whichever of the two list heads is smaller. When one input list is finally empty, it appends the other.

Upvotes: 0

binaryjigsaw
binaryjigsaw

Reputation: 11

So your current solution will return a sorted list if both input lists are sorted. If the input lists aren't sorted, you've got 2 options, sort the input lists individually, then merge them as you are already, or merge them unsorted, and sort the new list.

It seems more reasonable to merge unsorted lists and then sort them as one, so here is the solution. I've used a quick implementation of quicksort, but you could use whatever sorting algorithm you wish.

--takes 2 sorted or unsorted lists, merges them, then sorts them
merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge x [] = sort x
merge [] y = sort y
merge x y = sort (x ++ y)

-- where first element of list is pivot
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (x:xs) = sort [x'|x'<-xs, x'<=x] ++ [x] ++ sort [x'|x'<-xs, x'>x]

There are many ways to do this, and this way has the downside of having to resort the list even if the lists were already sorted. You could get around this by checking if lists are sorted, then sorting them if needed. I hope this answer helps.

Upvotes: 0

Related Questions