Example inefficient?

[turion]

https://github.com/haskell/play-haskell/blob/c0341e70b083961b7ecb0aa7e051e620a3e16135/play-haskell-server/static/play-index.ts#L42

Shouldn't this be:

toright (x:xs) = second (x :) (toleft xs)

Otherwise the lists aren't split into evenly sized parts, which I guess is only O(n^2) and not O(n log n).

[tomsmeding]

Uh, oops :) What do you think of this improvement? As a side-effect this actually also removes the need for the Bifunctor import. https://play.haskell.org/saved/j4vMomi2

EDIT: The quicksort example is actually also O(n^2) of course because of the dumb pivot selection, but fixing that would introduce lots of unnecessary complexity to a simple example

[turion]

What do you think of this improvement? As a side-effect this actually also removes the need for the Bifunctor import.

Yes, that's a great improvement!

The quicksort example is actually also O(n^2)

I guess it's only O(n^2) worst case? Which is fine I think. Selecting a clever pivot (median guess or whatever) would obfuscate it.

[turion]

The quicksort example is actually also O(n^2)

I guess it's only O(n^2) worst case?

You could also make the example data a bit more complicated:

  let unsorted = [9,7..1] ++ [2,4..10]

But I think it's fine to have a book algorithm in a straightforward implementation even if it's not the most efficient one possible.

[tomsmeding]

I guess it's only O(n^2) worst case?

For sure. And O(n) best-case, which is more than one can say of mergesort. :)

I'll change the top-down mergesort example to the thing I linked, then. Thanks for scrutinising my code :)