title: Why does Haskell use mergesort instead of quicksort?
body: <p>In <a href="https://en.wikibooks.org/wiki/Haskell" rel="noreferrer">Wikibooks' <em>Haskell</em></a>, there is <a href="https://en.wikibooks.org/wiki/Haskell/Higher-order_functions" rel="noreferrer">the following claim</a>:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p><strong>What is the underlying reason in Haskell to use mergesort over quicksort?</strong> 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.</p>
  
  <p>There was <a href="https://softwareengineering.stackexchange.com/questions/180417/fastest-haskell-library-sort-implementation">a related question on softwareengineering.SE</a>, but it wasn't really about <em>why</em> mergesort is used.</p>
  
  <p>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.</p>
  
  <p><strong>Edit:</strong> Here are my implementations of mergesort and quicksort:</p>
  
  <pre class="lang-hs prettyprint-override"><code>mergesort :: Ord a =&gt; [a] -&gt; [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 =&gt; [a] -&gt; [a] -&gt; [a]
  merge ls [] = ls
  merge [] vs = vs
  merge first@(l:ls) second@(v:vs)
      | l &lt; v = l : merge ls second
      | otherwise = v : merge first vs
  
  quicksort :: Ord a =&gt; [a] -&gt; [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 &lt; pivot = [elem:less, greater]
              | otherwise = [less, elem:greater]
  
  enumerate :: [a] -&gt; [(Int, a)]
  enumerate = zip [0..]
  </code></pre>
  
  <p><strong>Edit <s>2</s> 3:</strong> I was asked to provide timings for my implementations versus the sort in <code>Data.List</code>. Following @Will Ness' suggestions, I compiled <a href="https://gist.github.com/rwbogl/a7e4fb66c4b606da2f084242111ebe55" rel="noreferrer">this gist</a> with the <code>-O2</code> flag, changing the supplied sort in <code>main</code> each time, and executed it with <code>+RTS -s</code>. The sorted list was a cheaply-created, pseudorandom <code>[Int]</code> list with 2^20 elements. The results were as follows:</p>
  
  <ul>
  <li><code>Data.List.sort</code>: 0.171s</li>
  <li><code>mergesort</code>: 1.092s (~6x slower than <code>Data.List.sort</code>)</li>
  <li><code>quicksort</code>: 1.152s (~7x slower than <code>Data.List.sort</code>)</li>
  </ul>