+sortBy cmp l = mergesort cmp l
+sort l = mergesort compare l
+
+{-
+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, the results of which are
+shown below (* means it didn't finish successfully - in all cases this
+was due to a stack overflow).
+
+If I heap profile the random_list case with only 10000 then I see
+random_list peaks at using about 2.5M of memory, whereas in the same
+program using List.sort it uses only 100k.
+
+Input style Input length Sort data Sort alg User time
+stdin 10000 random_list sort 2.82
+stdin 10000 random_list mergesort 2.96
+stdin 10000 sorted sort 31.37
+stdin 10000 sorted mergesort 1.90
+stdin 10000 revsorted sort 31.21
+stdin 10000 revsorted mergesort 1.88
+stdin 100000 random_list sort *
+stdin 100000 random_list mergesort *
+stdin 100000 sorted sort *
+stdin 100000 sorted mergesort *
+stdin 100000 revsorted sort *
+stdin 100000 revsorted mergesort *
+func 10000 random_list sort 0.31
+func 10000 random_list mergesort 0.91
+func 10000 sorted sort 19.09
+func 10000 sorted mergesort 0.15
+func 10000 revsorted sort 19.17
+func 10000 revsorted mergesort 0.16
+func 100000 random_list sort 3.85
+func 100000 random_list mergesort *
+func 100000 sorted sort 5831.47
+func 100000 sorted mergesort 2.23
+func 100000 revsorted sort 5872.34
+func 100000 revsorted mergesort 2.24
+-}