> In fact, I'm not aware of an algorithm
that is as simple as Shell sort, and at
the same time much faster than O(n^2).

My favorite is heap sort, guaranteed O(n
log(n)) average case and worst case, meets
the Gleason bound and, thus, is the
fastest possible sort based on comparing
pairs of keys (in one of volumes of D.
Knuth, The Art of Computer Programming).

You mentioned simple: The logic of the
heap data structure and its corresponding
code seem to be relatively simple.

Of course, radix sort does not work by
"comparing pairs of keys", may be regarded
as O(n), and, check this, may also be
stable. Of course, radix sort was the
algorithm of the IBM punched card
sorting machine so maybe goes back to
before 1900 and, thus, is likely the
oldest of the common sorting algorithms.

Below (in a separate post) is code for

ai_heap_sort02

which is an (ascending integer) heap sort
routine.

Right, this code is for only ascending,
integers, and arrays and, thus, is far
from the practice of generic code, e.g.,
as in

https://en.wikipedia.org/wiki/Generic_programming

The advantages of generic code my work
doesn't really need. Once I wrote some
generic code, and that experience was
enough!

The code is in Microsoft's Visual Basic
.NET.

Why Visual Basic .NET?

I have written some C code. There are
claims that the programming language C has
idiosyncratic syntax. Whatever it has,
I don't like its syntax. I.e., supposedly

i = ++j+++++k++

is legal -- increase j and k by 1, add the
results, assign the result to i, and then
increase j and k by 1 again -- but when I
tested this on two different C compilers I
got different results. If the compilers
can't agree on the syntax, I don't want to
try to understand it! Besides, C is
supposed to be really simple, close to
assembly language, and highly portable,
and ambiguity I observed for

i = ++j+++++k++

conflicts with those attributes! Besides,
that syntax gets the grand prize for not
just idiosyncratic but obscure,
ugly, outrageous,
etc.!

Maybe C and C++ are essential for Windows
internals and for Windows applications
that make direct use of the System32 API,
but I've never written such code since my
background is applied math software.

Thus, also I don't like the related syntax
of C++ or C#.

The syntax of Visual Basic .NET (VB) is
more traditional, more like the original
Basic, then Fortran, Algol, Pascal, and
PL/I (maybe my favorite).

Thus, VB is relatively easy to teach,
learn, read, and write, and these
attributes might be considered important
in a large project!

Whatever the syntax of VB is, there are
claims that VB and C# have equivalent
semantics and differ only in syntactic
sugar. I.e., supposedly there is a
source code translator program than can
translate code in either of VB or C# to
the other.

So, for my project, code to run on
Windows, I am writing in VB instead of C#.

Also below (in a separate post)
is code

Function obj_heap_insert

Here I use the heap data structure, the
main idea in heap sort, to maintain a
priority queue. So, with this code can
look at 20 million objects one at a time
and end up with, e.g., the 20 largest.
Uh, how else to do that???!!!

Right, this code starts to be a little big
generic.

Right, operating on the heap data
structure can hurt possibly desired main
memory and cache memory locality of
reference, but there is at least one
modification of modifying operations on a
heap that speed up what otherwise might be
the case of a heap large enough to need
virtual memory.

All this code appears to run correctly. I
have later versions modified, longer, less
easy to read, to use an error handling
technique I cooked up -- really simple, I
wouldn't recommend for large projects and
it will likely become a case of technical
debt if my work grows a lot!

Uh, my view, a judgment call, is that the
article and my post here go deeper into
sorting than we should. I want to declare
sorting as a plenty well enough
understood, solved problem and move on to
other challenges.