I assumed that we were talking about
in place sorting.

"I feel your pain." As I tried
to explain, the first time I saw
big-O notation taken seriously as
the main metric for evaluating the
actual running time of
actual code on actual
data on an actual computer,
I had your reaction, that
the constants are important
and the big-O criterion, not good.

There's another point: The
silent assumption of the big-O criterion
is that we are interested in (A) something
fundamental about algorithms, just the
algorithms, and not (B) actual running time
of actual code on actual data on actual
computers.

And big progress in algorithms is also
important and, as we know, in some
cases can give much better performance
gains in real computing than anything
a programmer can do without the big progress.

And we have a great example: There
were days before heap sort, shell sort,
quicksort when the in place sorting
algorithm people coded were bubble sort
or something closely related and also O(n^2).
Then in practice, the difference was just
huge.

Early in my career, I ran into that at
Georgetown University: A prof had coded
up some software for teaching statistics
and had used the IBM Scientific Subroutine
Package (SSP) for a most of the actual
calculations. One of the SSP routines
was to find ranks, and it had two
loops, each essentially bubble sort.
In testing, the thing ran all lunch time.

Well, the data to be ranked was
32 bit integers, and an array index
was a 16 bit integer. So, I was
able to do a tricky overlay of
two 16 bit integers on the 32 bit
data, use heap sort, and get O( n ln(n) ).
In actually running time on nearly
any possible real data, my code
as so much faster than IBM's
SSP that I blew the doors off the
SSP.

Lesson 1: O( n ln(n) ) instead of O( n^2 )
can be much better in practice.

Lesson 2: Progress in big-O in algorithms
can be terrific stuff.

Back to practice, early in writing the
software for my startup, I tried to
write a polymorphic version of heap
sort. I wrote in Microsoft's Visual
Basic .NET. For the data type to
be sorted, I passed just the type
object. The software ran correctly
right away. Then I did some careful
timings -- the software commonly ran
ballpark 10 times longer than I
would have guessed. What the heck?
Well, the run time was smart enough
to figure out the actual data type
and do the comparison, but the overhead
here was enormous. Then I learned
that for polymorphic code I was
supposed to write some interfaces,
one for each data type to be sorted,
and for sorting a particular data
type pass the corresponding interface.
Okay. My confusion was that that use
of an interface didn't sound
polymorphic to me and sounded
no different than what I'd long
done passing entry variables
in PL/I and Fortran. Okay, for
polymorphism, use interfaces.
And in the code of the interface,
have to work essentially without
strong typing, essentially with
untyped pointers. Okay -- been there,
done that, in both PL/I and Fortran;
I was surprised that a serious
object oriented language with
polymorphism would have essentially
just syntactic sugar over what I'd
been doing in PL/I and Fortran. Okay.
Lesson learned: There are cases of
hype in parts of programming languages.

Heck, in PL/I my approach to sort an
array of PL/I structures would be
to pass a PL/I structure that
had an element variable that was
an entry variable to a procedure
that would do the comparisons.
That is, could have some conventions
that would let PL/I structures
be self-describing. Then
could write code that was more
general. Maybe under
the covers, that's just what's
going in the Microsoft common language
run time (CLR) that Visual Basic .NET
used for me without letting me know
-- more syntactic sugar?

So, when I rewrote my polymorphic
heap sort to do the comparisons
with a passed interface, the performance
got okay. Still, I have
non-polymorphic versions for the
more important element data types,
and they are faster in just they
way you emphasized. Yup, been
there, done that.

So, I, too, was concerned about actual
running time of actual data. But
for the algorithm itself, I
was still using just heap sort
and didn't try to write a
hybrid routine that sometimes
might exploit, say, radix sort.

On the pros and cons of using
big-O for the only criterion,
there's a big example in
linear programming:
In practice, the simplex
algorithm is fantastically
fast. Intuitively, in practice,
the early
iterations in effect focus
what to do to get to the
optimal solution (assuming feasibility,
no unboundedness, etc.).
But due to some work
of Klee and Minty, the worst
case of simplex is exponential
and just awful. Intuitively
the Klee and Minty examples
trick simplex into making
really bad choices!

So, there
was research to find a polynomial
algorithm for linear programming.
Eventually there was
an ellipsoid algorithm that
was polynomial but the constant
was so high that whenever
in practice ellipsoid beat
simplex both ran too long
to be practical.

So, really, the concern about simplex
and the effort for ellipsoid was
as progress just in algorithms and
in the big-O criterion. And in practice,
right away, the constant was
so large that ellipsoid was a flop.

Still, in algorithms, people
are straining to do better in
the sense of
the big-O criterion. Of course
the biggest effort here is
to find an algorithm that shows
that P = NP,
maybe the one of the most important
problems in both math and computer
science,
based on big-O for some polynomial.

With all of that, I decided in
my own work, for something
as simple as sorting, just to
go with heap sort, maybe even
a polymorphic heap sort.
Indeed, with all the emphasis on
polymorphism, people can't be
very concerned about constants! :-)!