On 12/04/2015 02:50 AM, Minas Mina wrote:
I agree -- putting the complexity (eh, running time) to the primitive's
name seems like a bad idea.
I believe that stability is a more important "feature" of a sorting
algorithm than its running time, because you can make implications about
it and use them for your own algorithms (I use it for implementing delta
compression) and affects the output.
Running time is still a good guarantee to have, but if `sort` runs
O(n^2) or O(nlogn) is not going to affect how your output will look like!
Sort is almost always assumed to take n log n time. The problem is when
you combine simpler operations, e.g. inserting elements at the front in
a loop.
Andrei
