I wrote that long post trying to explain
my attitude on sorting software from
50,000 or so feet up and, in particular,
why I have been happy just to use heap
sort and forget about looking for anything
faster on average.

I was reluctant to read the documentation
in your GitHub submission if only because
in my software development I have never
needed or used GitHub.

Also, I was reluctant to believe that
there could be any version of quicksort
that would have worst case running time of
O( n ln(n) ).

Why reluctant to believe?

First, sure, the usual version of
quicksort has us select a pivot value
for a partition from a "median of three"
keys from that partition.

Second, sure: For a good pivot value,
we want essentially the median of the keys
in the partition we are trying to split
into two partitions. And, sure, the
median of three approach to selecting a
pivot value is an approximation to the
median we really want and, thus, a
relatively good pivot value. So this
approach to selecting a pivot value
promises on average to get faster average
running times. Fine. Faster on average
is good. Terrific.

But this pivot selection rule says next to
nothing about worst case running time, and,
for claiming worst case running time of O(
n ln(n) ), this is a biggie issue.

Third, with this median of three approach
to selecting pivot values, we can think of
bad arrays of input keys that will cause
quicksort to run in time no faster than O(
n^2 ). Then maybe we can think of other
ways to select pivot values that result in
a new version of quicksort, a version that
runs in O( n ln(n) ) again on the bad
arrays. But with this change, here's the
problem: We are lacking a proof that the
worst case running time of the new version
of quicksort has worst case running time
of O( n ln(n) ).

That is, our new version of quicksort is
good for some old cases of bad arrays
but may have created for itself some new
cases of bad arrays. So, with no proof,
the new version of quicksort may also have
worst case running time of O( n^2 ) like
the old version did. The main difference
might be that the bad arrays for the new
version are more complicated to construct
than the bad arrays for the old case.

But I just looked at the file README.MD
you suggested. I see two issues:

First Issue:

> When a new pivot is chosen it's compared
to the greatest element in the partition
before it. If they compare equal we can
derive that there are no elements smaller
than the chosen pivot. When this happens
we switch strategy for this partition, and
filter out all elements equal to the
pivot.

If I understand this statement correctly,
I suspect that for some arrays of input
keys, the resulting algorithm won't
actually sort the keys. That is, we won't
have a sorting algorithm.

Second Issue:

> While this technically still allows for
a quadratic worst case, the chances of it
happening are astronomically small.

For proving worst case running time of O(
n ln(n) ), "astronomically small" is
irrelevant. Maybe your remark
"astronomically small" is just a side
comment and not relevant to PDQSORT having
worst case running time of O( n ln(n) ),
but from your documentation I can't easily
tell.

> A bad partition occurs when the position
of the pivot after partitioning is under
12.5% (1/8th) percentile or over 87,5%
percentile - the partition is highly
unbalanced. When this happens we will
shuffle four elements at fixed locations
for both partitions. This effectively
breaks up many patterns. If we encounter
more than log(n) bad partitions we will
switch to heap sort.

For this and the associated documentation,
I don't see a solid argument that PDQSORT
has worst case running time of O( n ln(n) ).

For some work, a big-O guarantee on worst
case performance is a biggie, as in
crucial to human life. Such a guarantee
is essentially a theorem in applied math
called computer science. A good example
of how to prove such theorems is, of
course, in D. Knuth, The Art of Computer
Programming, Volume 3, Sorting and
Searching.

Again, I have been happy just to use heap
sort and forget about looking for anything
faster on average.