Hacker News Reader

Comment by ionfish | Hacker News Reader

Obligatory comment pointing out that the fabled "quicksort" example in Haskell is not actually quicksort proper since it's not in-place.

View on HN

Obligatory comment about quicksort being excessively popular because of its catchy name, and all-too-often delivering inferior performance on large datasets due to partial orderings & bad pivot choices.

Obligatory comment about how sorting algorithm speed is far more important when dealing with incredibly large datasets, spanning across multiple machines. Uninsightful (and perhaps glib) point about how Machines Are So Fast These Days that even Bubble Sort appears fast for medium-sized datasets.

Cleverly-worded comment about how Merge Sort is not the sort of sort to let you down in a jam, and how it is particularly suited to distributed computation (where the overhead of allocation is rendered meaningless by the I/O requirements).

Genuine appreciation for concise recapitulation. I felt I could hear the Tivo fast-forward beep-boop sound while reading your comment.

Is it actually possible to implement quicksort in a pure functional language like Haskell (with immutable data structures)? Sorting in place would seem to involve mutating the list every time two values are swapped.

Yes. For example, the vector package provides mutable arrays:

http://hackage.haskell.org/package/vector-0.7.0.1

Mutability is attained by using the ST monad. The ST monad uses mutable memory, but since it does not allow other interactions with the outside world, its value can be extracted (unlike the IO monad). When you are done with the modification of the vector, it can be frozen to obtain a pure vector.

The IO monad can also be used, but not if you want to return a pure value.

A good tutorial can be found at:

http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector...

I used mutable vectors in the ST monad in maximum entropy training software, and they are really performant.

What blew my mind about the ST monad is that despite its promise of single-threading, it still allows for recursive division of labor.

I was like, "Wait. Wait. Waaaiiiitt. How does it do that?"

Haskell is designed to quarantine side effects, not remove them altogether. There's a special monad for building data structures that are mutable at creation time but appear immutable outside that block of code. In normal circumstances, you'd probably still have to copy the contents of the input into a new array before sorting it, though. So, it would still be less memory efficient on large inputs.

Haskell has mutable data structures; you could easily implement in-place quicksort with vectors, arrays, or pointers.

Not to mention that Haskell's sort function is actually quite a bit more complex than the stereotypical "quicksort" example shown.

For reference, Data.List.sort in GHC: http://www.haskell.org/ghc/docs/7.0.2/html/libraries/base-4....

It's still short and sweet ;).

C++'s std::sort in turn is a lot more complex than the quicksort example shown.

To be fair, that is because it is a carefully tuned combination of 3 sort routines (quicksort, heapsort, insertion sort), and also optimisations to avoid unnecessary checks for pointers reaching the end of arrays where they can be avoided.

I would be impressed if a sort which used the same 3 combined techniques could be faster.

(Of course, there might be better sorts, such as TimSort, but that's a change of algorithm, not language).

I think timsort is trying to optimize on comparison counts, because comparisons might call back into Python code, which is expensive. Other sorting algorithms optimize different operations.

Not only is it not proper quicksort, it's very memory inefficient.

Depends on your GC and compiler.

I'd argue that it's a good thing to use an algorithm that is efficient in and of itself. (And perhaps a language which invites the use of such an algorithm.)

The efficiency of algorithms depends on the language / model of computation you are using.

For an extreme example, the best way to write an efficient matrix multiplication in Fortran is to write a naive matrix multiplication. The compiler will recognize the pattern, and transform it.

Reply on news.ycombinator.com