Talk:Merge sort (Haskell)

From LiteratePrograms
Jump to: navigation, search

I haven't tested this at all yet (or even compiled it). Type signatures still to come as well... --Allan McInnes (talk) 23:30, 3 March 2006 (PST)

A problem with splitting the list into odd- and even-positioned elements is that it breaks stable sorting: given a predicate string-length<=, for example, and the list ["aaa","bbb","ccc"], you get ["aaa","ccc","bbb"] back. Thus the trick of having a copy of the list you consume two elements at a time, in order to split the list in the middle. -- Salimma 09:19, 4 March 2006 (PST)

Ah. Good point. Thanks - I didn't catch that subtlety :-( I should probably have just used the standard Haskell splitAt, but I was trying to make things a little more clear. I'll look at rewriting with the two-list version. --Allan McInnes (talk) 11:27, 4 March 2006 (PST)
hijacker
hijacker
hijacker
hijacker