Pfthb

I was thinking about quicksort not finding the exact midpoint for pivot.
Any effort to find exact midpoint as pivot slows down quicksort & is not worth it.

So is it possible to accomplish that using heapsort & is it any worthwhile?
I selected heapsort because it can find next max/min in logarithmic time.

If we divide heapsort array into 2 parts.

1) In the left half, we find max heap. (n/2-1 comparisons)
2) In the right half, we find min heap. (n/2-1 comparisons)
3) While 
 (max in left half is < min in right half)
 -- swap max in left half with min in right half
 -- heapify the swapped elements in respective halves 
 (i.e. find next max in left half 
 & find next min in right half). 
 
 end while loop.

When this loop ends, we have two completely disjoint halves.
There is no improvement so far than regular heapsort.

1) We can complete the remaining heapification in each half (log n/2 for remaining elements at most).
So any element that was in the correct half would heapify log n/2 at most instead of log n at most.

This is one optimization

The other optimization can be

2) We may be able to recursively apply this in each disjoint half (divide & concur).
3) Also we can exclude the central 2 elements from subsequent disjoint partitions, because they are already in their invariant location
e.g. 1-16 (n-1 comparisons to find max/min)
we have 1-7 & 8-16 partition in the first step
second step may have 4 partitions
(7 & 8 are in invariant location) (so n-3 comparisons to find max/min)
3 step may have 8 partitions
with 4 more more elements in invariant location.
So n-7 comparisons to find max/min in each partition.

I am trying to implemented this,
But I would like to know if anybody sees any theoretical advantage in this approach or it is no good.

For already sorted, I see there will be no swapping & we just go on finding max/min in subsequent halves
For descending sort, we see all elements getting swapped & heapified with no chance to divide & concur. So it will be as good or as bad as normal heapsort. this may be the worst case.

For all others, we will see any any improvement after max/min swapping stops.

You have an O(n) pass that creates two heaps. Then in the worst case you have (n/2)*(log n/2) replacements in each of the two heaps. At this point you've already done n*log(n/2) operations, and you haven't even started sorting. You will require another n*log(n/2) operations to finish the sort.

Contrast that to heapsort, which has the O(n) pass that creates a single heap, and then n*log(n) operations to complete sorting the array.

I see no particular advantage to building two heaps of size n/2 rather than a single heap of size n. In the best case you have more complicated code that has the same or worse asymptotic complexity, and is unlikely to give you a real-world increase in performance.