1. I think the stack usage of Quicksort is O(log(n)). Which means it is impossible to blow up the stack unless your dataset is bigger than the number of atoms in the universe (but in that case how are you keeping it in memory?)
2. For example in Java when you call Arrays.sort() this is called:
http://cr.openjdk.java.net/~alanb/6905046/webrev/src/share/c...
(It apparently uses recursion)
I know quicksort, but not on this level: these guys researched lots of different quicksort implementations and optmized the hell out of it. This implmenetation is way longer to begin with than my naive quicksort implementation would be and is called 'dual pivot quicksort', which I did not hear about until now, despite I know how the traditional quicksort works.
2. Yup, it recurses, and it looks to me as if it's vulnerable to blowing out the stack in the worst cases. However, it's quite a sophisticated implementation and in practice you're probably only going to see the worst cases if you feed it actively malicious input (see, e.g., http://www.cs.dartmouth.edu/~doug/mdmspe.pdf for a paper about doing this).
[EDITED to add: (1) A little discussion of that paper on HN is at http://news.ycombinator.com/item?id=1723305. (2) I don't know whether McIlroy's "killer adversary" would actually work against this dual-pivot algorithm without some modification; it depends on how well its heuristic for telling when the pivot is being found works against this algorithm. I'd guess that it does work.]
This could be solved with randomization though. (Onlyy a few lines of code needs to be changed.)
In that earlier HN discussion there was an extended (and frankly rather fruitless) debate between me and another poster about whether McIlroy's adversary can rightly be said to break randomized quicksort; that was basically terminological, and what is not in question is that if you take a typical randomized-quicksort implementation and feed it McIlroy's evil comparator, you will get order-n^2 performance.
A malicious attacker may even craft data that causes this behaviour, if they know the library / variant being used.
Consider a quicksort algorithm that takes the first element in each partition and uses that as the pivot.
When given sorted data it will iterate as:
Notation: (left set) _pivot_ (right set)
Input: 1 2 3 4 5
() _1_ (2 3 4 5) 1 is chosen as pivot, all elements in right set
1 () _2_ (3 4 5) 2 is chosen as pivot...
1 2 () _3_ (4 5)
1 2 3 () _4_ (5)
So that's n-1 levels of recursion with n elements -> O(n)
Even if you take the 'middle' (left-middle if even number) element as the pivot it's possible to construct a patalogical case:-
Input: 4 2 1 3 5
() _1_ (4 2 3 5) 2 is next pivot for right partition
1 () _2_ (4 3 5) 3 is next pivot for right partition
1 2 () _3_ (4 5) 4 is next pivot as left of middle for even number of elements
1 2 3 () _4_ (5) ...
On the other point; I'm not saying that every implementation of quicksort out there is susceptible. I'm saying that there are quite a few implementations that are in common use that are just the basic quick sort algorithm and can be made to blow through available finite stack space given large enough datasets or even semi-pathalogical input cases.
The majority of problems can be done away with by choosing a random pivot point from the set, that way it's very unlikely (but not impossible) to achieve a pathalogical case. However, such an implementation becomes indeterministic in that there's a very small but non-zero chance that the random pivots chosen will select items from the array in relative order and lead to too many levels of recursion. To me something that blows up only very rarely, and virtually impossible to replicate, is a nightmare to debug and fix. I'd much rather put the right algorithm in there to begin with to avoid this possibility completely.
There are plenty of other tricks you can implement to avoid cases like this, e.g. checking that the pivot creates partitions with at least 10% of elements in; that greatly reduces the number of possible recursions
But you'd be surprised at the number of sort implementations out there in the real world which are just implementations of the basic quicksort algorithm.
What language do you use which doesn't already have an optimized version of quicksort or equivalent?
Other languages do sorting in one of several ways:-
1) Just wrapper libc's qsort() and so suffer the same problem if that's susceptible.
2) Implement the naive recursive stack-gobbling quicksort in their own language as a module/package/import/library.
3) Implement their own sorting algorithm that avoids lots of recursive calls or does the tricks to pick suitable pivots, etc.
It's #1 and #2 that tend to suffer from problems when sorting large datasets, or the pathalogical cases that pinpoint the absolute worst in the design of the algorithm.
Oh, I am mainly familiar with GNU C library. Wasn't aware others were shipping recursive qsort implementation, especially considering that a non recursive qsort is an undergrad level exercise.
An understanding big-O notation is very important if you go searching for sorting algorithms and land on a page that has an overview of sorting functions but listing bogosort as O(n!) and insertion sort as O(n^2), both relatively easy to implement, and this relatively complicated iterative[1] quick sort that's listed as O(n log n). Without other clues someone might just implement the one that looks easiest, and it works fine on their test set of 20 elements, but blows up in the future as their application/site grows and slows to a crawl sorting through millions of rows with an insertion sort.
Or, one of the most recent questions in the Mathematics part of the exam made me snigger because someone I work with was asking what bignum library was easiest to use. Rather than just answering their question (I prefer GMP myself) I asked why; they wanted to do the equivalent of log( x^300 ) and so they needed to compute x^300 first and then take the log of it; floating-point was giving slightly inaccurate answers to what was expected when they took the log of the intermediate result. It was even worse when they tried to do log( x^9125 ) - or whatever exponent is used for daily interest on a 25 year mortgage to account for leap days.
To put it another way. Without the knowledge you end up googling, and implementing, the wrong thing. You may get the right answer/outcome in the end but it may be horribly inefficient. Or, worse, an inaccurate answer/outcome; and you may not even know.
Hammering the insertion sort analogy home; you can profile and optimise an insertion sort all you like, it's still never going to approach the speed of quicksort on mid-large datasets. Huge datasets are another matter, someone stuck with "quicksort is the best" is going to struggle when faced with hundreds of millions of rows and there are things less pessimal than quicksort.
Knowledge of processor architectures, caching and how hash tables are implemented means you know not to use a hash when a simple array will suffice; but I've seen this done plenty of times.
Etc, etc, etc.
Out of the 15 questions so far there's only been two or three that the knowledge of wouldn't have helped me at some point in my development over the last 15 years. Of those that haven't applied to me I can see why they would be important to other fields and other people.
It's one of the major reasons I decided to do a full Maths degree (part-time via correspondence) to complement the Comp Sci degree I got ~15 years ago. It's not just the obvious useful stuff like calculus, group and set theory, graphs and networks, etc. Whilst I thought that the mechanics part of the Maths degree wouldn't be very useful in my job I was surprised at how useful and ubiquitous [non-]homogenous second-order linear differential equations are in modeling things that are relevant to my job (populations -> user base, hysteresis, etc).
No doubt others find huge amounts of other knowledge in other subjects that is directly applicable to IT; psychology, education, design to name but a few.
The right choice of algorithm, and implementation, in a critical part of your code could mean the difference between having 64GB of memory per server or getting by with 16GB. It could mean 100 servers to manage your 1M users, or 10 servers; the difference between 100 servers and 10 servers to manage your 1M users could mean the difference between making a profit and making a loss. These could be the differences between your idea succeeding or disappearing.
1. Another one of my common things I do at work is replacing quicksort implemented using recursion with an iterative version so that the stack doesn't keep getting blown on large datasets. I like it when people encounter this problem and find out that stacks are finitely sized and not as big as they'd hoped they would be. "But that means..." is a great thing to hear.