How does it compare to an O(1) space version of quicksort?

quicksort is not a stable sort (http://en.wikipedia.org/wiki/Stable_sort#Stability)

Quicksort is worst case O(n^2) time, unless you incorporate something like Quickselect for your pivot (which no one ever does, because it makes it relatively complicated. Have you ever seen an O(n log n) guaranteed quicksort implemented? I haven't - best I've seen is median-of-3 or median-of-5 pivots - or randomized). Furthermore, I've never seen an O(1) space version of quicksort and I'm not sure one can exist -- see, e.g. http://stackoverflow.com/questions/11455242/is-it-possible-t...

The meaningful comparison would actually be to Heapsort, which is in-place, O(1) space, and NOT stable - though much, much, simpler.

ADDED:

Anyone who uses quicksort should read this gem from Doug McIlroy, which elicits an O(n^2) behaviour from most quicksort implementations: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf -

Many/most widely used “quicksort” implementations are actually introsort (in particular, `std::sort` is), and thus O(nlogn) worst case.

There is no O(1) space version of quicksort.

Came from Unix. A "shell to the kernel" that only exposed the outer layer.

Have a source?

Not really, the internet points to this doc: http://www.multicians.org/shell.html Where Louis Pouzin of Multics claims to have coined it.

Ken Thompson describes it here http://v6shell.org/history/unix/unix.pdf

Looking around, this seems more interesting (implying it is a metaphorical name of a prophet's shell listening): http://unix.stackexchange.com/questions/14934/why-was-the-wo...

I like to think if it as a last call for attention. Remember academics are attention addicts.

Clay Mathematics Page still lists it as unsolved. I know of dozens of "solutions" that have not been accepted. Do we know if this is just submitted or actually accepted by the scientific community.

When will mercurial learn that these things should be default. One of the only reasons I moved to git was I didn't have to hand hold people setting up all the extensions.

Whenever I teach hg, I just give them a template .hgrc and the first lesson is about putting their name in there. It's a one-time cost for any Mercurial user.

The Mercurial dev team is very conservative. The reason some of these extensions aren't default yet are due to bugs or because they don't work well on Windows or because they require the user to learn some advanced usage (e.g. an improper rebase can result in apparent data loss to the uninitiated). Some of these just have a plain yucky UI, e.g. histedit's UI is very close to "git rebase -i". It would be much nicer if it had some sort of curses interface instead.

Mercurial is in this for long haul, and it gets better all the time. As its extensions mature, they'll be turned on by default. Right now, it's a matter of flipping them on.

In function currently_available_bikes, you see him curling:

https://citibikenyc.com/stations/json

But this is all wrong. "Academic Freedom" means that you are free to publish your findings in an objective way without having to please your investors.

Of course you have to do things that are interesting and impactful and the funding is less now than it has been in the decade prior, but that is much different than saying that academic freedom means doing whatever you want. I can just imagine Michelangelo writing this blog during his agony of painting the Sistine Chapel.