sorting algos

[saminny]

What are the use cases when a particular sorting algorithm is preferred - merge sort vs quick sort vs heap sort vs introsort, etc? Is there a recommended guide in using them based on the size, type of data strucutre, available memory and cache, and CPU performance.

thanks,

Sam

[tummychow]

If you are asking for practical purposes, you can save yourself some time and include the <algorithm> header, then just use the STL sort algo.
If you are asking about the actual overhead incurrence of sorting algorithms, I am not entirely sure. Try asking wikipedia.
In general there is going to be a sort whose time to perform is better than any other but I'm not sure what it is. Could you clarify your criteria? Those are questions to ask about computer hardware not sorting algorithms.

[helios]

Quick sort is good for most circumstances. If the relative order of the elements needs to be preserved (e.g. 2312 becoming 1223), merge sort is better, since quick sort may not be stable.
There are several choices when you have a structure that needs to remain sorted as new elements are added.

http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Of course, as tummychow pointed out, it's usually best to just use the algorithms provided by the language.

[tummychow]

Helios that page is awesome, I can't believe I never took a look at that...
By the way here's my question: what's the point of stable sorting? If the elements are the same does it have any effect if they end up in the wrong order?

[R0mai]

tummychow wrote:

If the elements are the same does it have any effect if they end up in the wrong order?

Comparing equal doesn't necessary means they are the same.

[helios]

Just because two elements are equal according to the sorting criterion, it doesn't mean that they're completely equal.

http://en.wikipedia.org/wiki/Stable_sort#Stability

[tummychow]

Isn't that a problem with the chosen criteria then? (although I can see where in some cases it would be useful)
Also what is the algorithm used for the stl algorithm?

[jsmith]

See

http://www.sgi.com/tech/stl/sort.html

[moorecm]

Here's a nice little graphical comparison of a few sorting functions:
http://www.sorting-algorithms.com/

[kempofighter]

By the way here's my question: what's the point of stable sorting? If the elements are the same does it have any effect if they end up in the wrong order?

I'll be honest. I have never needed stable_sort but it is also provided by the language. Read up on that or perform a google search on that algorithm and perhaps you'll find some interesting threads where programmers describe why they needed to use it.

[PanGalactic]

I have found stable sorting useful for testing data manipulation programs across multiple platforms. A given input file should have the same stable sort output across all platforms whereas a non-stable sort may not. You can easily see differences in output this way to detect platform specific bugs.