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
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++
i = ++j+++++k++
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.