Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Especially when writing 'standard' (non-HPC) applications, do you consider what sorting algorithm to pick, or just settle with quicksort (which is what most libraries just call sort)? To some extent it may be profitable in specific situations, but on the other hand proper optimization requires some time to analyse the problem and make benchmarks.

share|improve this question

6 Answers 6

up vote 11 down vote accepted

In general, using the default methods unless there is a specific need to do something more exotic keeps everything a lot more readable/understandable down the road IMHO.

If you experience (or in some cases, strongly suspect) that you have a performance problem that is the time to add complexity.

On the other hand, if you are using a low enough language that there is not a built-in sort for the kind of objects you need to sort try to pick one or two that cover all your bases and implement those.

share|improve this answer

Although it obviously doesn't matter to the bits and timeslices. I find merge sort to be easier to write and understand than quicksort. So if I'm going to write my own sorting algorithm I'd use that.

share|improve this answer
    
Viva mergesort! And a mildly better constant term, and no horrific worst-case. –  Frank Shearar Oct 14 '10 at 16:16

This is the time to pull out the classic quote about premature optimization. In most cases, it really doesn't matter. Heck, with the speed of CPUs these days, you could probably bubble sort most data sets and not really notice much. But when you're sorting really large data sets, and sort performance starts to become an issue, then you should definitely look at other options.

share|improve this answer
    
Bubble sort? Its performance is the worst for average and worst-case, and equals insertion sort for best case. There is no reason that it should be used. –  Hippo Nov 20 '10 at 4:47
1  
@Hippo: I wasn't actually advocating using bubble sort. I meant that modern computers are fast enough that in most cases it doesn't matter how slow your algorithm is because the user won't notice. –  Mason Wheeler Nov 20 '10 at 4:59
    
How about Bogosort? –  dsimcha Mar 23 '11 at 19:20

At least in a competently written library, I'd expect the built-in sort to be implemented as an Introsort rather than just a Quicksort. The difference rarely matters much, but Introsort eliminates the bad worst-case performance of Quicksort with minimal effect on the more common cases.

To answer your question, however: yes -- that's what you should usually start with, and until/unless you have profiler results indicating that it's a problem, that's where it should remain.

share|improve this answer

Always call the library routines provided, unless you have very, very good reason not to do so (and you need to document why it is so).

This is because sorting algorithms are hard to get absolutely right. There was a bug in the Java quicksort with very large datasets, which was identified, fixed and delivered to customers by Sun, so you didn't have to.

Also the default sort in Java 7 has been upgraded to a newer, better sort. Also for free.

Unless the default sort is provably not good enough for you, stick with it.

share|improve this answer

At a conference once I heard a nice story about this.

At Microsoft someone was writing a VB app (c. VB 3) and mailed a bunch of people saying that he had a load of values and he wanted them to appear in the combobox in order, how should he go about it.

Everyone dived for their old computer science text books, looking up highly efficient routines and porting them to Visual Basic and mailing them to him. One guys just mailed back "how many values in the combobox?".

"About 50" came the reply.

"Just set the sorted property to TRUE".

In 99.9999% of instances sorting is best done using a library, control or in the SQL select as the performance difference between the library routine and anything you write will be negligible and the effort and maintenance overhead will massively outweigh the consequences.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.