The resulting order of equal elements has absolutely nothing to do with the comparator function. The comparator only implies which elements are equal. A stable algorithm can only change order if there's a strict b<a relationship, where a is initially before b. An unstable algorithm is free to change order as long as !(a<b). This is why pivoting is allowed in quicksort.How would the comparator consider the original order without having to modify the element structure to include an index? It's the algorithm that takes care of this by abiding by the criteria I mentioned above.Most data structures don't have a natural ordering that applies to all situations. Not only that, but it's a waste of time to consider every member of a data structure when sorting a list because you're generally only concerned with a few at a time. I almost always find myself sorting a list of data structures based on a subset of the members, rather than using a comparator that compares every last member.

Kevin Barry

That's why I said, "minimum running time". It is true that in the worst case, quick sort is just select sort run with recursion. It might even have an exponential running time because of the recursion (like with fibonacci numbers) but I can't say for certain.

Of course, this is most unlikely if you choose a random pivot. You should also avoid advancing your pointers if the element's key is equal to the pivot since that can also lead to lop-sided partitioning. (It turns out that it is better to simply exchange elements who's keys are equal to the pivot than to test for the equality).

Jonathon Shewchuck gives a very good lecture on quicksort in this YOU TUBE.

I am also impressed with heapsort. It might not be as fast as quicksort but it still runs in NlogN time and with its in-array sorting and lack of recursion, it makes an ideal candidate in situations where memory is tight.

The irony is that these fancy sorting routines are often at their worst when dealing with already sorted data.