Why does Haskell use mergesort instead of quicksort?

Clash Royale CLAN TAG#URR8PPP

up vote
39
down vote

favorite

8

In Wikibooks' Haskell, there is the following claim:

Data.List offers a sort function for sorting lists. It does not use quicksort; rather, it uses an efficient implementation of an algorithm called mergesort.

What is the underlying reason in Haskell to use mergesort over quicksort? Quicksort usually has better practical performance, but maybe not in this case. I gather that the in-place benefits of quicksort are hard (impossible?) to do with Haskell lists.

There was a related question on softwareengineering.SE, but it wasn't really about why mergesort is used.

I implemented the two sorts myself for profiling. Mergesort was superior (around twice as fast for a list of 2^20 elements), but I'm not sure that my implementation of quicksort was optimal.

Edit: Here are my implementations of mergesort and quicksort:

mergesort :: Ord a => [a] -> [a]
mergesort = 
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
 where size = div (length l) 2
 (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls = ls
merge vs = vs
merge first@(l:ls) second@(v:vs)
 | l < v = l : merge ls second
 | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort = 
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
 where pivotIndex = div (length l) 2
 pivot = l !! pivotIndex
 [less, greater] = foldl addElem [, ] $ enumerate l
 addElem [less, greater] (index, elem)
 | index == pivotIndex = [less, greater]
 | elem < pivot = [elem:less, greater]
 | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

Edit 2 3: I was asked to provide timings for my implementations versus the sort in Data.List. Following @Will Ness' suggestions, I compiled this gist with the -O2 flag, changing the supplied sort in main each time, and executed it with +RTS -s. The sorted list was a cheaply-created, pseudorandom [Int] list with 2^20 elements. The results were as follows:

• 
  Data.List.sort: 0.171s


• 
  mergesort: 1.092s (~6x slower than Data.List.sort)


• 
  quicksort: 1.152s (~7x slower than Data.List.sort)

performance sorting haskell

share|improve this question

edited 2 days ago

asked Sep 8 at 17:25

rwbogl

31229

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  How did you implement quicksort on singly-linked lists?
  – melpomene
  Sep 8 at 17:29
  

  
  
  
  


• 
  
  
  

  
  6
  

  
  
  
  
  
  

  
  merge sort can be optimized by splitting the list at even/odd index, which can be done in a single pass with direct recursion, avoiding the two-pass approach above (length, splitAt). Anyway, I guess performance here drove the choice of algorithm. Quicksort is fast because it can be made in-place (with arrays). On lists, it's slower. Some people argue that it should not be called "quicksort" unless it's in-place. Perhaps you can run a few benchmarks yourself.
  – chi
  Sep 8 at 17:51
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  I suggest you benchmark your quicksort against Data.List.sort.
  – melpomene
  Sep 8 at 18:15
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  The sort important implementation was not switched from quicksort to mergesort without benchmarking. :) Also, a nice property of the current implementation is that it has O(n) complexity for (nearly) sorted inputs.
  – augustss
  Sep 9 at 1:20
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  The Ghc's implementation of mergesort also uses an algorithm to detect sequences. Making it very efficient sorting almost sorted lists.
  – JohEker
  Sep 9 at 14:41
  

  
  
  
  

 | 
show 8 more comments

up vote
39
down vote

favorite

8

In Wikibooks' Haskell, there is the following claim:

Data.List offers a sort function for sorting lists. It does not use quicksort; rather, it uses an efficient implementation of an algorithm called mergesort.

What is the underlying reason in Haskell to use mergesort over quicksort? Quicksort usually has better practical performance, but maybe not in this case. I gather that the in-place benefits of quicksort are hard (impossible?) to do with Haskell lists.

There was a related question on softwareengineering.SE, but it wasn't really about why mergesort is used.

I implemented the two sorts myself for profiling. Mergesort was superior (around twice as fast for a list of 2^20 elements), but I'm not sure that my implementation of quicksort was optimal.

Edit: Here are my implementations of mergesort and quicksort:

mergesort :: Ord a => [a] -> [a]
mergesort = 
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
 where size = div (length l) 2
 (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls = ls
merge vs = vs
merge first@(l:ls) second@(v:vs)
 | l < v = l : merge ls second
 | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort = 
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
 where pivotIndex = div (length l) 2
 pivot = l !! pivotIndex
 [less, greater] = foldl addElem [, ] $ enumerate l
 addElem [less, greater] (index, elem)
 | index == pivotIndex = [less, greater]
 | elem < pivot = [elem:less, greater]
 | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

Edit 2 3: I was asked to provide timings for my implementations versus the sort in Data.List. Following @Will Ness' suggestions, I compiled this gist with the -O2 flag, changing the supplied sort in main each time, and executed it with +RTS -s. The sorted list was a cheaply-created, pseudorandom [Int] list with 2^20 elements. The results were as follows:

• 
  Data.List.sort: 0.171s


• 
  mergesort: 1.092s (~6x slower than Data.List.sort)


• 
  quicksort: 1.152s (~7x slower than Data.List.sort)

performance sorting haskell

share|improve this question

edited 2 days ago

asked Sep 8 at 17:25

rwbogl

31229

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  How did you implement quicksort on singly-linked lists?
  – melpomene
  Sep 8 at 17:29
  

  
  
  
  


• 
  
  
  

  
  6
  

  
  
  
  
  
  

  
  merge sort can be optimized by splitting the list at even/odd index, which can be done in a single pass with direct recursion, avoiding the two-pass approach above (length, splitAt). Anyway, I guess performance here drove the choice of algorithm. Quicksort is fast because it can be made in-place (with arrays). On lists, it's slower. Some people argue that it should not be called "quicksort" unless it's in-place. Perhaps you can run a few benchmarks yourself.
  – chi
  Sep 8 at 17:51
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  I suggest you benchmark your quicksort against Data.List.sort.
  – melpomene
  Sep 8 at 18:15
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  The sort important implementation was not switched from quicksort to mergesort without benchmarking. :) Also, a nice property of the current implementation is that it has O(n) complexity for (nearly) sorted inputs.
  – augustss
  Sep 9 at 1:20
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  The Ghc's implementation of mergesort also uses an algorithm to detect sequences. Making it very efficient sorting almost sorted lists.
  – JohEker
  Sep 9 at 14:41
  

  
  
  
  

 | 
show 8 more comments

up vote
39
down vote

favorite

8

up vote
39
down vote

favorite

8

8

In Wikibooks' Haskell, there is the following claim:

Data.List offers a sort function for sorting lists. It does not use quicksort; rather, it uses an efficient implementation of an algorithm called mergesort.

What is the underlying reason in Haskell to use mergesort over quicksort? Quicksort usually has better practical performance, but maybe not in this case. I gather that the in-place benefits of quicksort are hard (impossible?) to do with Haskell lists.

There was a related question on softwareengineering.SE, but it wasn't really about why mergesort is used.

I implemented the two sorts myself for profiling. Mergesort was superior (around twice as fast for a list of 2^20 elements), but I'm not sure that my implementation of quicksort was optimal.

Edit: Here are my implementations of mergesort and quicksort:

mergesort :: Ord a => [a] -> [a]
mergesort = 
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
 where size = div (length l) 2
 (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls = ls
merge vs = vs
merge first@(l:ls) second@(v:vs)
 | l < v = l : merge ls second
 | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort = 
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
 where pivotIndex = div (length l) 2
 pivot = l !! pivotIndex
 [less, greater] = foldl addElem [, ] $ enumerate l
 addElem [less, greater] (index, elem)
 | index == pivotIndex = [less, greater]
 | elem < pivot = [elem:less, greater]
 | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

Edit 2 3: I was asked to provide timings for my implementations versus the sort in Data.List. Following @Will Ness' suggestions, I compiled this gist with the -O2 flag, changing the supplied sort in main each time, and executed it with +RTS -s. The sorted list was a cheaply-created, pseudorandom [Int] list with 2^20 elements. The results were as follows:

• 
  Data.List.sort: 0.171s


• 
  mergesort: 1.092s (~6x slower than Data.List.sort)


• 
  quicksort: 1.152s (~7x slower than Data.List.sort)

performance sorting haskell

share|improve this question

edited 2 days ago

asked Sep 8 at 17:25

rwbogl

31229

In Wikibooks' Haskell, there is the following claim:

Data.List offers a sort function for sorting lists. It does not use quicksort; rather, it uses an efficient implementation of an algorithm called mergesort.

What is the underlying reason in Haskell to use mergesort over quicksort? Quicksort usually has better practical performance, but maybe not in this case. I gather that the in-place benefits of quicksort are hard (impossible?) to do with Haskell lists.

There was a related question on softwareengineering.SE, but it wasn't really about why mergesort is used.

I implemented the two sorts myself for profiling. Mergesort was superior (around twice as fast for a list of 2^20 elements), but I'm not sure that my implementation of quicksort was optimal.

Edit: Here are my implementations of mergesort and quicksort:

mergesort :: Ord a => [a] -> [a]
mergesort = 
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
 where size = div (length l) 2
 (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls = ls
merge vs = vs
merge first@(l:ls) second@(v:vs)
 | l < v = l : merge ls second
 | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort = 
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
 where pivotIndex = div (length l) 2
 pivot = l !! pivotIndex
 [less, greater] = foldl addElem [, ] $ enumerate l
 addElem [less, greater] (index, elem)
 | index == pivotIndex = [less, greater]
 | elem < pivot = [elem:less, greater]
 | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

Edit 2 3: I was asked to provide timings for my implementations versus the sort in Data.List. Following @Will Ness' suggestions, I compiled this gist with the -O2 flag, changing the supplied sort in main each time, and executed it with +RTS -s. The sorted list was a cheaply-created, pseudorandom [Int] list with 2^20 elements. The results were as follows:

• 
  Data.List.sort: 0.171s


• 
  mergesort: 1.092s (~6x slower than Data.List.sort)


• 
  quicksort: 1.152s (~7x slower than Data.List.sort)

performance sorting haskell

performance sorting haskell

share|improve this question

edited 2 days ago

asked Sep 8 at 17:25

rwbogl

31229

share|improve this question

edited 2 days ago

asked Sep 8 at 17:25

rwbogl

31229

share|improve this question

share|improve this question

edited 2 days ago

edited 2 days ago

edited 2 days ago

asked Sep 8 at 17:25

rwbogl

31229

asked Sep 8 at 17:25

rwbogl

31229

asked Sep 8 at 17:25

rwbogl

31229

31229

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  How did you implement quicksort on singly-linked lists?
  – melpomene
  Sep 8 at 17:29
  

  
  
  
  


• 
  
  
  

  
  6
  

  
  
  
  
  
  

  
  merge sort can be optimized by splitting the list at even/odd index, which can be done in a single pass with direct recursion, avoiding the two-pass approach above (length, splitAt). Anyway, I guess performance here drove the choice of algorithm. Quicksort is fast because it can be made in-place (with arrays). On lists, it's slower. Some people argue that it should not be called "quicksort" unless it's in-place. Perhaps you can run a few benchmarks yourself.
  – chi
  Sep 8 at 17:51
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  I suggest you benchmark your quicksort against Data.List.sort.
  – melpomene
  Sep 8 at 18:15
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  The sort important implementation was not switched from quicksort to mergesort without benchmarking. :) Also, a nice property of the current implementation is that it has O(n) complexity for (nearly) sorted inputs.
  – augustss
  Sep 9 at 1:20
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  The Ghc's implementation of mergesort also uses an algorithm to detect sequences. Making it very efficient sorting almost sorted lists.
  – JohEker
  Sep 9 at 14:41
  

  
  
  
  

 | 
show 8 more comments

• 
  
  
  

  
  4
  

  
  
  
  
  
  

  
  How did you implement quicksort on singly-linked lists?
  – melpomene
  Sep 8 at 17:29
  

  
  
  
  


• 
  
  
  

  
  6
  

  
  
  
  
  
  

  
  merge sort can be optimized by splitting the list at even/odd index, which can be done in a single pass with direct recursion, avoiding the two-pass approach above (length, splitAt). Anyway, I guess performance here drove the choice of algorithm. Quicksort is fast because it can be made in-place (with arrays). On lists, it's slower. Some people argue that it should not be called "quicksort" unless it's in-place. Perhaps you can run a few benchmarks yourself.
  – chi
  Sep 8 at 17:51
  
  

  
  
  
  


• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  I suggest you benchmark your quicksort against Data.List.sort.
  – melpomene
  Sep 8 at 18:15
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  The sort important implementation was not switched from quicksort to mergesort without benchmarking. :) Also, a nice property of the current implementation is that it has O(n) complexity for (nearly) sorted inputs.
  – augustss
  Sep 9 at 1:20
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  The Ghc's implementation of mergesort also uses an algorithm to detect sequences. Making it very efficient sorting almost sorted lists.
  – JohEker
  Sep 9 at 14:41
  

  
  
  
  

4

4

How did you implement quicksort on singly-linked lists?
– melpomene
Sep 8 at 17:29

How did you implement quicksort on singly-linked lists?
– melpomene
Sep 8 at 17:29

6

6

merge sort can be optimized by splitting the list at even/odd index, which can be done in a single pass with direct recursion, avoiding the two-pass approach above (length, splitAt). Anyway, I guess performance here drove the choice of algorithm. Quicksort is fast because it can be made in-place (with arrays). On lists, it's slower. Some people argue that it should not be called "quicksort" unless it's in-place. Perhaps you can run a few benchmarks yourself.
– chi
Sep 8 at 17:51

merge sort can be optimized by splitting the list at even/odd index, which can be done in a single pass with direct recursion, avoiding the two-pass approach above (length, splitAt). Anyway, I guess performance here drove the choice of algorithm. Quicksort is fast because it can be made in-place (with arrays). On lists, it's slower. Some people argue that it should not be called "quicksort" unless it's in-place. Perhaps you can run a few benchmarks yourself.
– chi
Sep 8 at 17:51

3

3

I suggest you benchmark your quicksort against Data.List.sort.
– melpomene
Sep 8 at 18:15

I suggest you benchmark your quicksort against Data.List.sort.
– melpomene
Sep 8 at 18:15

2

2

The sort important implementation was not switched from quicksort to mergesort without benchmarking. :) Also, a nice property of the current implementation is that it has O(n) complexity for (nearly) sorted inputs.
– augustss
Sep 9 at 1:20

The sort important implementation was not switched from quicksort to mergesort without benchmarking. :) Also, a nice property of the current implementation is that it has O(n) complexity for (nearly) sorted inputs.
– augustss
Sep 9 at 1:20

1

1

The Ghc's implementation of mergesort also uses an algorithm to detect sequences. Making it very efficient sorting almost sorted lists.
– JohEker
Sep 9 at 14:41

The Ghc's implementation of mergesort also uses an algorithm to detect sequences. Making it very efficient sorting almost sorted lists.
– JohEker
Sep 9 at 14:41

 | 
show 8 more comments

4 Answers
4

active

oldest

votes

up vote
47
down vote



accepted

In imperative languages, Quicksort is performed in-place by mutating an array. As you demonstrate in your code sample, you can adapt Quicksort to a pure functional language like Haskell by building singly-linked lists instead, but this is not as fast.

On the other hand, Mergesort is not an in-place algorithm: a straightforward imperative implementation copies the merged data to a different allocation. This is a better fit for Haskell, which by its nature must copy the data anyway.

Let's step back a bit: Quicksort's performance edge is "lore" -- a reputation built up decades ago on machines much different from the ones we use today. Even if you use the same language, this kind of lore needs rechecking from time to time, as the facts on the ground can change. The last benchmarking paper I read on this topic had Quicksort still on top, but its lead over Mergesort was slim, even in C/C++.

Mergesort has other advantages: it doesn't need to be tweaked to avoid Quicksort's O(n^2) worst case, and it is naturally stable. So, if you lose the narrow performance difference due to other factors, Mergesort is an obvious choice.

share|improve this answer

edited Sep 8 at 18:49

answered Sep 8 at 18:06

comingstorm

19.2k12755

• 
  
  
  

  
  18
  

  
  
  
  
  
  

  
  Another note: You can implement mergesort in such a way that head (sort xs) is O(n) in a lazy language.
  – melpomene
  Sep 8 at 18:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  what do you mean by "naturally" stable? it is very easy to do the initial split wrong, like e.g. "splitting the list at even/odd index".
  – Will Ness
  Sep 8 at 19:00
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Yes, but if you do the implementation right, you can get your stability "for free". With Quicksort (and other unstable sorts like Heapsort), you must explicitly track the original index to stabilize the sort. This dings the performance enough that, if you need the stability, you might as well use Mergesort.
  – comingstorm
  Sep 8 at 19:11
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Actually, the not-in-place version of Quicksort above is (or can be made) stable, unlike the usual in-place Quicksort! I was alerted to this from following the link from K. A. Buhr's answer to the old Haskell implementation, which notes that its qsort (similar to the question's quicksort) is stable.
  – comingstorm
  Sep 8 at 20:25
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  yeah, I wasn't arguing against it. the runs discovery and bottom-up merging is specifically named "natural" in the cs.tufts.edu/~nr/cs257/archive/olin-shivers/msort.ps paper, even quoting the 1982 O'Keefe implementation mentioned in the docs (which is how I found that paper). for the simple list-based quicksort (which is a deforested tree sort really), all we have to do is use < and >= (and not <= and >) in the partitioning.
  – Will Ness
  Sep 9 at 1:45
  
  

  
  
  
  

add a comment | 

up vote
18
down vote

I think @comingstorm's answer is pretty much on the nose, but here's some more info on the history of GHC's sort function.

In the source code for Data.OldList, you can find the implementation of sort and verify for yourself that it's a merge sort. Just below the definition in that file is the following comment:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <igloo@earth.li>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it's performance...

So, originally a functional quicksort was used (and the function qsort is still there, but commented out). Ian's benchmarks showed that his mergesort was competitive with quicksort in the "random list" case and massively outperformed it in the case of already sorted data. Later, Ian's version was replaced by another implementation that was about twice as fast, according to additional comments in that file.

The main issue with the original qsort was that it didn't use a random pivot. Instead it pivoted on the first value in the list. This is obviously pretty bad because it implies performance will be worst case (or close) for sorted (or nearly sorted) input. Unfortunately, there are a couple of challenges in switching from "pivot on first" to an alternative (either random, or -- as in your implementation -- somewhere in "the middle"). In a functional language without side effects, managing a pseudorandom input is a bit of a problem, but let's say you solve that (maybe by building a random number generator into your sort function). You still have the problem that, when sorting an immutable linked list, locating an arbitrary pivot and then partitioning based on it will involve multiple list traversals and sublist copies.

I think the only way to realize the supposed benefits of quicksort would be to write the list out to a vector, sort it in place (and sacrifice sort stability), and write it back out to a list. I don't see that that could ever be an overall win. On the other hand, if you already have data in a vector, then an in-place quicksort would definitely be a reasonable option.

share|improve this answer

answered Sep 8 at 18:40

K. A. Buhr

13.6k11236

add a comment | 

up vote
1
down vote

On a singly-linked list, mergesort can be done in place. What's more, naive implementations scan over half the list in order to get the start of the second sublist, but the start of the second sublist falls out as a side effect of sorting the first sublist and does not need extra scanning. The one thing quicksort has going over mergesort is cache coherency. Quicksort works with elements close to each other in memory. As soon as an element of indirection enters into it, like when you are sorting pointer arrays instead of the data itself, that advantage becomes less.

Mergesort has hard guarantees for worst-case behavior, and it's easy to do stable sorting with it.

share|improve this answer

answered 2 days ago

user10339366

add a comment | 

up vote
0
down vote

Short answer:

Quicksort is advantageous for arrays (in-place, fast, but not worst-case optimal). Mergesort for linked lists (fast, worst-case optimal, stable, simple).

Quicksort is slow for lists, Mergesort is not in-place for arrays.

share|improve this answer

answered 20 hours ago

Yves Daoust

34.7k62454

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52237695%2fwhy-does-haskell-use-mergesort-instead-of-quicksort%23new-answer', 'question_page');

);

Post as a guest

Name Email

4 Answers
4

active

oldest

votes

4 Answers
4

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
47
down vote



accepted

In imperative languages, Quicksort is performed in-place by mutating an array. As you demonstrate in your code sample, you can adapt Quicksort to a pure functional language like Haskell by building singly-linked lists instead, but this is not as fast.

On the other hand, Mergesort is not an in-place algorithm: a straightforward imperative implementation copies the merged data to a different allocation. This is a better fit for Haskell, which by its nature must copy the data anyway.

Let's step back a bit: Quicksort's performance edge is "lore" -- a reputation built up decades ago on machines much different from the ones we use today. Even if you use the same language, this kind of lore needs rechecking from time to time, as the facts on the ground can change. The last benchmarking paper I read on this topic had Quicksort still on top, but its lead over Mergesort was slim, even in C/C++.

Mergesort has other advantages: it doesn't need to be tweaked to avoid Quicksort's O(n^2) worst case, and it is naturally stable. So, if you lose the narrow performance difference due to other factors, Mergesort is an obvious choice.

share|improve this answer

edited Sep 8 at 18:49

answered Sep 8 at 18:06

comingstorm

19.2k12755

• 
  
  
  

  
  18
  

  
  
  
  
  
  

  
  Another note: You can implement mergesort in such a way that head (sort xs) is O(n) in a lazy language.
  – melpomene
  Sep 8 at 18:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  what do you mean by "naturally" stable? it is very easy to do the initial split wrong, like e.g. "splitting the list at even/odd index".
  – Will Ness
  Sep 8 at 19:00
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Yes, but if you do the implementation right, you can get your stability "for free". With Quicksort (and other unstable sorts like Heapsort), you must explicitly track the original index to stabilize the sort. This dings the performance enough that, if you need the stability, you might as well use Mergesort.
  – comingstorm
  Sep 8 at 19:11
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Actually, the not-in-place version of Quicksort above is (or can be made) stable, unlike the usual in-place Quicksort! I was alerted to this from following the link from K. A. Buhr's answer to the old Haskell implementation, which notes that its qsort (similar to the question's quicksort) is stable.
  – comingstorm
  Sep 8 at 20:25
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  yeah, I wasn't arguing against it. the runs discovery and bottom-up merging is specifically named "natural" in the cs.tufts.edu/~nr/cs257/archive/olin-shivers/msort.ps paper, even quoting the 1982 O'Keefe implementation mentioned in the docs (which is how I found that paper). for the simple list-based quicksort (which is a deforested tree sort really), all we have to do is use < and >= (and not <= and >) in the partitioning.
  – Will Ness
  Sep 9 at 1:45
  
  

  
  
  
  

add a comment | 

up vote
47
down vote



accepted

In imperative languages, Quicksort is performed in-place by mutating an array. As you demonstrate in your code sample, you can adapt Quicksort to a pure functional language like Haskell by building singly-linked lists instead, but this is not as fast.

On the other hand, Mergesort is not an in-place algorithm: a straightforward imperative implementation copies the merged data to a different allocation. This is a better fit for Haskell, which by its nature must copy the data anyway.

Let's step back a bit: Quicksort's performance edge is "lore" -- a reputation built up decades ago on machines much different from the ones we use today. Even if you use the same language, this kind of lore needs rechecking from time to time, as the facts on the ground can change. The last benchmarking paper I read on this topic had Quicksort still on top, but its lead over Mergesort was slim, even in C/C++.

Mergesort has other advantages: it doesn't need to be tweaked to avoid Quicksort's O(n^2) worst case, and it is naturally stable. So, if you lose the narrow performance difference due to other factors, Mergesort is an obvious choice.

share|improve this answer

edited Sep 8 at 18:49

answered Sep 8 at 18:06

comingstorm

19.2k12755

• 
  
  
  

  
  18
  

  
  
  
  
  
  

  
  Another note: You can implement mergesort in such a way that head (sort xs) is O(n) in a lazy language.
  – melpomene
  Sep 8 at 18:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  what do you mean by "naturally" stable? it is very easy to do the initial split wrong, like e.g. "splitting the list at even/odd index".
  – Will Ness
  Sep 8 at 19:00
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Yes, but if you do the implementation right, you can get your stability "for free". With Quicksort (and other unstable sorts like Heapsort), you must explicitly track the original index to stabilize the sort. This dings the performance enough that, if you need the stability, you might as well use Mergesort.
  – comingstorm
  Sep 8 at 19:11
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Actually, the not-in-place version of Quicksort above is (or can be made) stable, unlike the usual in-place Quicksort! I was alerted to this from following the link from K. A. Buhr's answer to the old Haskell implementation, which notes that its qsort (similar to the question's quicksort) is stable.
  – comingstorm
  Sep 8 at 20:25
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  yeah, I wasn't arguing against it. the runs discovery and bottom-up merging is specifically named "natural" in the cs.tufts.edu/~nr/cs257/archive/olin-shivers/msort.ps paper, even quoting the 1982 O'Keefe implementation mentioned in the docs (which is how I found that paper). for the simple list-based quicksort (which is a deforested tree sort really), all we have to do is use < and >= (and not <= and >) in the partitioning.
  – Will Ness
  Sep 9 at 1:45
  
  

  
  
  
  

add a comment | 

up vote
47
down vote



accepted

up vote
47
down vote



accepted

In imperative languages, Quicksort is performed in-place by mutating an array. As you demonstrate in your code sample, you can adapt Quicksort to a pure functional language like Haskell by building singly-linked lists instead, but this is not as fast.

On the other hand, Mergesort is not an in-place algorithm: a straightforward imperative implementation copies the merged data to a different allocation. This is a better fit for Haskell, which by its nature must copy the data anyway.

Let's step back a bit: Quicksort's performance edge is "lore" -- a reputation built up decades ago on machines much different from the ones we use today. Even if you use the same language, this kind of lore needs rechecking from time to time, as the facts on the ground can change. The last benchmarking paper I read on this topic had Quicksort still on top, but its lead over Mergesort was slim, even in C/C++.

Mergesort has other advantages: it doesn't need to be tweaked to avoid Quicksort's O(n^2) worst case, and it is naturally stable. So, if you lose the narrow performance difference due to other factors, Mergesort is an obvious choice.

share|improve this answer

edited Sep 8 at 18:49

answered Sep 8 at 18:06

comingstorm

19.2k12755

In imperative languages, Quicksort is performed in-place by mutating an array. As you demonstrate in your code sample, you can adapt Quicksort to a pure functional language like Haskell by building singly-linked lists instead, but this is not as fast.

On the other hand, Mergesort is not an in-place algorithm: a straightforward imperative implementation copies the merged data to a different allocation. This is a better fit for Haskell, which by its nature must copy the data anyway.

Let's step back a bit: Quicksort's performance edge is "lore" -- a reputation built up decades ago on machines much different from the ones we use today. Even if you use the same language, this kind of lore needs rechecking from time to time, as the facts on the ground can change. The last benchmarking paper I read on this topic had Quicksort still on top, but its lead over Mergesort was slim, even in C/C++.

Mergesort has other advantages: it doesn't need to be tweaked to avoid Quicksort's O(n^2) worst case, and it is naturally stable. So, if you lose the narrow performance difference due to other factors, Mergesort is an obvious choice.

share|improve this answer

edited Sep 8 at 18:49

answered Sep 8 at 18:06

comingstorm

19.2k12755

share|improve this answer

share|improve this answer

edited Sep 8 at 18:49

edited Sep 8 at 18:49

edited Sep 8 at 18:49

answered Sep 8 at 18:06

comingstorm

19.2k12755

answered Sep 8 at 18:06

comingstorm

19.2k12755

answered Sep 8 at 18:06

comingstorm

19.2k12755

19.2k12755

• 
  
  
  

  
  18
  

  
  
  
  
  
  

  
  Another note: You can implement mergesort in such a way that head (sort xs) is O(n) in a lazy language.
  – melpomene
  Sep 8 at 18:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  what do you mean by "naturally" stable? it is very easy to do the initial split wrong, like e.g. "splitting the list at even/odd index".
  – Will Ness
  Sep 8 at 19:00
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Yes, but if you do the implementation right, you can get your stability "for free". With Quicksort (and other unstable sorts like Heapsort), you must explicitly track the original index to stabilize the sort. This dings the performance enough that, if you need the stability, you might as well use Mergesort.
  – comingstorm
  Sep 8 at 19:11
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Actually, the not-in-place version of Quicksort above is (or can be made) stable, unlike the usual in-place Quicksort! I was alerted to this from following the link from K. A. Buhr's answer to the old Haskell implementation, which notes that its qsort (similar to the question's quicksort) is stable.
  – comingstorm
  Sep 8 at 20:25
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  yeah, I wasn't arguing against it. the runs discovery and bottom-up merging is specifically named "natural" in the cs.tufts.edu/~nr/cs257/archive/olin-shivers/msort.ps paper, even quoting the 1982 O'Keefe implementation mentioned in the docs (which is how I found that paper). for the simple list-based quicksort (which is a deforested tree sort really), all we have to do is use < and >= (and not <= and >) in the partitioning.
  – Will Ness
  Sep 9 at 1:45
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  18
  

  
  
  
  
  
  

  
  Another note: You can implement mergesort in such a way that head (sort xs) is O(n) in a lazy language.
  – melpomene
  Sep 8 at 18:32
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  what do you mean by "naturally" stable? it is very easy to do the initial split wrong, like e.g. "splitting the list at even/odd index".
  – Will Ness
  Sep 8 at 19:00
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Yes, but if you do the implementation right, you can get your stability "for free". With Quicksort (and other unstable sorts like Heapsort), you must explicitly track the original index to stabilize the sort. This dings the performance enough that, if you need the stability, you might as well use Mergesort.
  – comingstorm
  Sep 8 at 19:11
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Actually, the not-in-place version of Quicksort above is (or can be made) stable, unlike the usual in-place Quicksort! I was alerted to this from following the link from K. A. Buhr's answer to the old Haskell implementation, which notes that its qsort (similar to the question's quicksort) is stable.
  – comingstorm
  Sep 8 at 20:25
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  yeah, I wasn't arguing against it. the runs discovery and bottom-up merging is specifically named "natural" in the cs.tufts.edu/~nr/cs257/archive/olin-shivers/msort.ps paper, even quoting the 1982 O'Keefe implementation mentioned in the docs (which is how I found that paper). for the simple list-based quicksort (which is a deforested tree sort really), all we have to do is use < and >= (and not <= and >) in the partitioning.
  – Will Ness
  Sep 9 at 1:45
  
  

  
  
  
  

18

18

Another note: You can implement mergesort in such a way that head (sort xs) is O(n) in a lazy language.
– melpomene
Sep 8 at 18:32

Another note: You can implement mergesort in such a way that head (sort xs) is O(n) in a lazy language.
– melpomene
Sep 8 at 18:32

1

1

what do you mean by "naturally" stable? it is very easy to do the initial split wrong, like e.g. "splitting the list at even/odd index".
– Will Ness
Sep 8 at 19:00

what do you mean by "naturally" stable? it is very easy to do the initial split wrong, like e.g. "splitting the list at even/odd index".
– Will Ness
Sep 8 at 19:00

2

2

Yes, but if you do the implementation right, you can get your stability "for free". With Quicksort (and other unstable sorts like Heapsort), you must explicitly track the original index to stabilize the sort. This dings the performance enough that, if you need the stability, you might as well use Mergesort.
– comingstorm
Sep 8 at 19:11

Yes, but if you do the implementation right, you can get your stability "for free". With Quicksort (and other unstable sorts like Heapsort), you must explicitly track the original index to stabilize the sort. This dings the performance enough that, if you need the stability, you might as well use Mergesort.
– comingstorm
Sep 8 at 19:11

2

2

Actually, the not-in-place version of Quicksort above is (or can be made) stable, unlike the usual in-place Quicksort! I was alerted to this from following the link from K. A. Buhr's answer to the old Haskell implementation, which notes that its qsort (similar to the question's quicksort) is stable.
– comingstorm
Sep 8 at 20:25

Actually, the not-in-place version of Quicksort above is (or can be made) stable, unlike the usual in-place Quicksort! I was alerted to this from following the link from K. A. Buhr's answer to the old Haskell implementation, which notes that its qsort (similar to the question's quicksort) is stable.
– comingstorm
Sep 8 at 20:25

yeah, I wasn't arguing against it. the runs discovery and bottom-up merging is specifically named "natural" in the cs.tufts.edu/~nr/cs257/archive/olin-shivers/msort.ps paper, even quoting the 1982 O'Keefe implementation mentioned in the docs (which is how I found that paper). for the simple list-based quicksort (which is a deforested tree sort really), all we have to do is use < and >= (and not <= and >) in the partitioning.
– Will Ness
Sep 9 at 1:45

yeah, I wasn't arguing against it. the runs discovery and bottom-up merging is specifically named "natural" in the cs.tufts.edu/~nr/cs257/archive/olin-shivers/msort.ps paper, even quoting the 1982 O'Keefe implementation mentioned in the docs (which is how I found that paper). for the simple list-based quicksort (which is a deforested tree sort really), all we have to do is use < and >= (and not <= and >) in the partitioning.
– Will Ness
Sep 9 at 1:45

add a comment | 

up vote
18
down vote

I think @comingstorm's answer is pretty much on the nose, but here's some more info on the history of GHC's sort function.

In the source code for Data.OldList, you can find the implementation of sort and verify for yourself that it's a merge sort. Just below the definition in that file is the following comment:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <igloo@earth.li>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it's performance...

So, originally a functional quicksort was used (and the function qsort is still there, but commented out). Ian's benchmarks showed that his mergesort was competitive with quicksort in the "random list" case and massively outperformed it in the case of already sorted data. Later, Ian's version was replaced by another implementation that was about twice as fast, according to additional comments in that file.

The main issue with the original qsort was that it didn't use a random pivot. Instead it pivoted on the first value in the list. This is obviously pretty bad because it implies performance will be worst case (or close) for sorted (or nearly sorted) input. Unfortunately, there are a couple of challenges in switching from "pivot on first" to an alternative (either random, or -- as in your implementation -- somewhere in "the middle"). In a functional language without side effects, managing a pseudorandom input is a bit of a problem, but let's say you solve that (maybe by building a random number generator into your sort function). You still have the problem that, when sorting an immutable linked list, locating an arbitrary pivot and then partitioning based on it will involve multiple list traversals and sublist copies.

I think the only way to realize the supposed benefits of quicksort would be to write the list out to a vector, sort it in place (and sacrifice sort stability), and write it back out to a list. I don't see that that could ever be an overall win. On the other hand, if you already have data in a vector, then an in-place quicksort would definitely be a reasonable option.

share|improve this answer

answered Sep 8 at 18:40

K. A. Buhr

13.6k11236

add a comment | 

up vote
18
down vote

I think @comingstorm's answer is pretty much on the nose, but here's some more info on the history of GHC's sort function.

In the source code for Data.OldList, you can find the implementation of sort and verify for yourself that it's a merge sort. Just below the definition in that file is the following comment:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <igloo@earth.li>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it's performance...

So, originally a functional quicksort was used (and the function qsort is still there, but commented out). Ian's benchmarks showed that his mergesort was competitive with quicksort in the "random list" case and massively outperformed it in the case of already sorted data. Later, Ian's version was replaced by another implementation that was about twice as fast, according to additional comments in that file.

The main issue with the original qsort was that it didn't use a random pivot. Instead it pivoted on the first value in the list. This is obviously pretty bad because it implies performance will be worst case (or close) for sorted (or nearly sorted) input. Unfortunately, there are a couple of challenges in switching from "pivot on first" to an alternative (either random, or -- as in your implementation -- somewhere in "the middle"). In a functional language without side effects, managing a pseudorandom input is a bit of a problem, but let's say you solve that (maybe by building a random number generator into your sort function). You still have the problem that, when sorting an immutable linked list, locating an arbitrary pivot and then partitioning based on it will involve multiple list traversals and sublist copies.

I think the only way to realize the supposed benefits of quicksort would be to write the list out to a vector, sort it in place (and sacrifice sort stability), and write it back out to a list. I don't see that that could ever be an overall win. On the other hand, if you already have data in a vector, then an in-place quicksort would definitely be a reasonable option.

share|improve this answer

answered Sep 8 at 18:40

K. A. Buhr

13.6k11236

add a comment | 

up vote
18
down vote

up vote
18
down vote

I think @comingstorm's answer is pretty much on the nose, but here's some more info on the history of GHC's sort function.

In the source code for Data.OldList, you can find the implementation of sort and verify for yourself that it's a merge sort. Just below the definition in that file is the following comment:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <igloo@earth.li>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it's performance...

So, originally a functional quicksort was used (and the function qsort is still there, but commented out). Ian's benchmarks showed that his mergesort was competitive with quicksort in the "random list" case and massively outperformed it in the case of already sorted data. Later, Ian's version was replaced by another implementation that was about twice as fast, according to additional comments in that file.

The main issue with the original qsort was that it didn't use a random pivot. Instead it pivoted on the first value in the list. This is obviously pretty bad because it implies performance will be worst case (or close) for sorted (or nearly sorted) input. Unfortunately, there are a couple of challenges in switching from "pivot on first" to an alternative (either random, or -- as in your implementation -- somewhere in "the middle"). In a functional language without side effects, managing a pseudorandom input is a bit of a problem, but let's say you solve that (maybe by building a random number generator into your sort function). You still have the problem that, when sorting an immutable linked list, locating an arbitrary pivot and then partitioning based on it will involve multiple list traversals and sublist copies.

I think the only way to realize the supposed benefits of quicksort would be to write the list out to a vector, sort it in place (and sacrifice sort stability), and write it back out to a list. I don't see that that could ever be an overall win. On the other hand, if you already have data in a vector, then an in-place quicksort would definitely be a reasonable option.

share|improve this answer

answered Sep 8 at 18:40

K. A. Buhr

13.6k11236

I think @comingstorm's answer is pretty much on the nose, but here's some more info on the history of GHC's sort function.

In the source code for Data.OldList, you can find the implementation of sort and verify for yourself that it's a merge sort. Just below the definition in that file is the following comment:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <igloo@earth.li>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it's performance...

So, originally a functional quicksort was used (and the function qsort is still there, but commented out). Ian's benchmarks showed that his mergesort was competitive with quicksort in the "random list" case and massively outperformed it in the case of already sorted data. Later, Ian's version was replaced by another implementation that was about twice as fast, according to additional comments in that file.

The main issue with the original qsort was that it didn't use a random pivot. Instead it pivoted on the first value in the list. This is obviously pretty bad because it implies performance will be worst case (or close) for sorted (or nearly sorted) input. Unfortunately, there are a couple of challenges in switching from "pivot on first" to an alternative (either random, or -- as in your implementation -- somewhere in "the middle"). In a functional language without side effects, managing a pseudorandom input is a bit of a problem, but let's say you solve that (maybe by building a random number generator into your sort function). You still have the problem that, when sorting an immutable linked list, locating an arbitrary pivot and then partitioning based on it will involve multiple list traversals and sublist copies.

I think the only way to realize the supposed benefits of quicksort would be to write the list out to a vector, sort it in place (and sacrifice sort stability), and write it back out to a list. I don't see that that could ever be an overall win. On the other hand, if you already have data in a vector, then an in-place quicksort would definitely be a reasonable option.

share|improve this answer

answered Sep 8 at 18:40

K. A. Buhr

13.6k11236

share|improve this answer

share|improve this answer

answered Sep 8 at 18:40

K. A. Buhr

13.6k11236

answered Sep 8 at 18:40

K. A. Buhr

13.6k11236

answered Sep 8 at 18:40

K. A. Buhr

13.6k11236

13.6k11236

add a comment | 

add a comment | 

up vote
1
down vote

On a singly-linked list, mergesort can be done in place. What's more, naive implementations scan over half the list in order to get the start of the second sublist, but the start of the second sublist falls out as a side effect of sorting the first sublist and does not need extra scanning. The one thing quicksort has going over mergesort is cache coherency. Quicksort works with elements close to each other in memory. As soon as an element of indirection enters into it, like when you are sorting pointer arrays instead of the data itself, that advantage becomes less.

Mergesort has hard guarantees for worst-case behavior, and it's easy to do stable sorting with it.

share|improve this answer

answered 2 days ago

user10339366

add a comment | 

up vote
1
down vote

On a singly-linked list, mergesort can be done in place. What's more, naive implementations scan over half the list in order to get the start of the second sublist, but the start of the second sublist falls out as a side effect of sorting the first sublist and does not need extra scanning. The one thing quicksort has going over mergesort is cache coherency. Quicksort works with elements close to each other in memory. As soon as an element of indirection enters into it, like when you are sorting pointer arrays instead of the data itself, that advantage becomes less.

Mergesort has hard guarantees for worst-case behavior, and it's easy to do stable sorting with it.

share|improve this answer

answered 2 days ago

user10339366

add a comment | 

up vote
1
down vote

up vote
1
down vote

On a singly-linked list, mergesort can be done in place. What's more, naive implementations scan over half the list in order to get the start of the second sublist, but the start of the second sublist falls out as a side effect of sorting the first sublist and does not need extra scanning. The one thing quicksort has going over mergesort is cache coherency. Quicksort works with elements close to each other in memory. As soon as an element of indirection enters into it, like when you are sorting pointer arrays instead of the data itself, that advantage becomes less.

Mergesort has hard guarantees for worst-case behavior, and it's easy to do stable sorting with it.

share|improve this answer

answered 2 days ago

user10339366

On a singly-linked list, mergesort can be done in place. What's more, naive implementations scan over half the list in order to get the start of the second sublist, but the start of the second sublist falls out as a side effect of sorting the first sublist and does not need extra scanning. The one thing quicksort has going over mergesort is cache coherency. Quicksort works with elements close to each other in memory. As soon as an element of indirection enters into it, like when you are sorting pointer arrays instead of the data itself, that advantage becomes less.

Mergesort has hard guarantees for worst-case behavior, and it's easy to do stable sorting with it.

share|improve this answer

answered 2 days ago

user10339366

share|improve this answer

share|improve this answer

answered 2 days ago

user10339366

answered 2 days ago

user10339366

answered 2 days ago

user10339366

add a comment | 

add a comment | 

up vote
0
down vote

Short answer:

Quicksort is advantageous for arrays (in-place, fast, but not worst-case optimal). Mergesort for linked lists (fast, worst-case optimal, stable, simple).

Quicksort is slow for lists, Mergesort is not in-place for arrays.

share|improve this answer

answered 20 hours ago

Yves Daoust

34.7k62454

add a comment | 

up vote
0
down vote

Short answer:

Quicksort is advantageous for arrays (in-place, fast, but not worst-case optimal). Mergesort for linked lists (fast, worst-case optimal, stable, simple).

Quicksort is slow for lists, Mergesort is not in-place for arrays.

share|improve this answer

answered 20 hours ago

Yves Daoust

34.7k62454

add a comment | 

up vote
0
down vote

up vote
0
down vote

Short answer:

Quicksort is advantageous for arrays (in-place, fast, but not worst-case optimal). Mergesort for linked lists (fast, worst-case optimal, stable, simple).

Quicksort is slow for lists, Mergesort is not in-place for arrays.

share|improve this answer

answered 20 hours ago

Yves Daoust

34.7k62454

Short answer:

Quicksort is advantageous for arrays (in-place, fast, but not worst-case optimal). Mergesort for linked lists (fast, worst-case optimal, stable, simple).

Quicksort is slow for lists, Mergesort is not in-place for arrays.

share|improve this answer

answered 20 hours ago

Yves Daoust

34.7k62454

share|improve this answer

share|improve this answer

answered 20 hours ago

Yves Daoust

34.7k62454

answered 20 hours ago

Yves Daoust

34.7k62454

answered 20 hours ago

Yves Daoust

34.7k62454

34.7k62454

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52237695%2fwhy-does-haskell-use-mergesort-instead-of-quicksort%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email