Thoughts about sorting algorithms

I was thinking about `heapsort` earlier. It's really a pretty sweet algorithm (I even implemented it earlier (and did not test it)).
* Like `quicksort`, (and unlike `mergesort`) it can be done in-place.
* Like `mergesort`, (and unlike `quicksort`) it has `O(nlogn)` runtime complexity.

If the range to be sorted doesn't fit in the cache, `heapsort` probably does worse than `mergesort`, because `mergesort` is mostly sequential access and `heapsort` does a lot of jumping around.

`mergesort` can also be modified to benefit from partially-sorted data. I bet a modified `mergesort` that leverages already-sorted subranges and uses `heapsort` to benefit from cache-locality when creating subranges to be merged would perform quite well!

I just googled hybrid sorts to see if this one already exists.

`introsort` is a hybrid sort that uses `quicksort` at the top level and switches to `heapsort` to handle degenerate `quicksort` cases and switches to `insertion sort` sort small subranges. This is a pretty cool algorithm for several reasons, but I particularly like that it does not require any additional memory.

`timsort` is a hybrid `mergesort` that detects sorted subranges and uses `insertion sort` to benefit from cache locality while creating subranges to be merged. This is obviously pretty close to what I mentioned above.

Notes:
* `heapsort` is not "stable"
* The wikipedia page on sorting algorithms:  https://en.wikipedia.org/wiki/Sorting_algorithm
* I've pasted by heapsort implementation because heapsort is cool (it probably has bugs). It would be much shorter using `std::make_heap`, `std::push_heap`, etc. But why not just call `std::sort` at that point?

```C++
#include <span>
#include <cassert>

auto heapsort(std::span<std::int32_t> range) -> void;
auto heapify(std::span<std::int32_t> range) -> void;
auto push_heap(std::span<std::int32_t> heapPlusExtra, std::size_t heapSize) -> void;
auto pop_heap(std::span<std::int32_t> heapPlusExtra, std::size_t heapSize) -> void;

auto heapsort(std::span<std::int32_t> range) -> void
{
    heapify(range);
    for (auto heapSize = range.size(); heapSize > 1; --heapSize) {
        pop_heap(range, heapSize);
    }
}
auto heapify(std::span<std::int32_t> range) -> void
{
    for (auto heapSize = std::size_t{1}; heapSize < range.size(); ++heapSize) {
        push_heap(range, heapSize);
    }
}
auto push_heap(std::span<std::int32_t> heapPlusExtra, std::size_t heapSize) -> void
{
    assert(heapSize >= 1);

    auto index = heapSize;
    while (index != 0 && heapPlusExtra[index / 2] < heapPlusExtra[index]) {
        std::swap(heapPlusExtra[index / 2], heapPlusExtra[index]);
        index /= 2;
    }
}
auto pop_heap(std::span<std::int32_t> heapPlusExtra, std::size_t heapSize) -> void
{
    assert(heapSize > 1);
    
    // Move back element to the root.
    auto index = 0;
    std::swap(heapPlusExtra[index], heapPlusExtra[heapSize]);
    
    auto rIndex = std::size_t{};
    while (rIndex = (index + 1) * 2, rIndex < heapSize) {
        auto lIndex = rIndex - 1;
        auto cIndex = (heapPlusExtra[lIndex] > heapPlusExtra[rIndex]) ? lIndex : rIndex;
        if (heapPlusExtra[cIndex] > heapPlusExtra[index]) {
            std::swap(heapPlusExtra[cIndex], heapPlusExtra[index]);
            index = cIndex;
        } else {
            break;
        }
    }
    
    // Handle case where index has only a left child. This may result in an extra compare,
    // but I think the bookkeeping to prevent it would hurt more than it would help.
    if (rIndex == heapSize) {
        auto lIndex = rIndex - 1;
        if (heapPlusExtra[lIndex] > heapPlusExtra[index]) {
            std::swap(heapPlusExtra[lIndex], heapPlusExtra[index]);
        }
    }
}
```