Since pdqsort, vqsort, and glide sort, the current state-of-the-art are driftsort and ipnsort.
I've integrated them into ClickHouse: https://github.com/ClickHouse/ClickHouse/pull/106650
There’s something sort of beautiful about mergesort and heapsort. Their names tell you what their main idea is, and how they work is immediately obvious.
Quicksort, on the other hand, has nothing beautiful about it and is named after it’s one redeeming feature (that it is quick for a lot of cases).
The in-place property can be utilized to make it very close to cache-oblivious algorithm.
Honest question, curious to hear about what that means to you.
Real answer: I tutored beginner programming students for a bit and I guess I just thought quicksort didn’t fit in very well.
Mergesort is an elegant and straightforward example of recursion. Heapsort—you can make a priority queue and then if you plop a heap in there, that’s heapsort. I like the story.
With quicksort, it isn’t that complicated or anything but it doesn’t feel like it embodies an idea in the way the other two do. And it is annoying that the real big-O cost of the popular sorting algorithm is n^2, and the bad case is really obvious. I guess there’s value to getting over the hump of “well heuristics are a thing and big-O doesn’t tell you everything” but I still don’t like it.
It feels like an optimization of merge sort for computers, rather than a different approach.
This is also reflected in the way that it’s usually taught. Normally merge sort is presented first, and quick sort follows from observations about what would happen if you picked different partition points instead of dividing them in half, and how you can reduce the additional space requirements.
Actual sense in which it’s first:
> Happily, modern instruction sets (Arm SVE, RISC-V V, x86 AVX-512) include a special instruction suitable for partitioning. Given a separate input of yes/no values (whether an element is less than the pivot), this "compress-store" instruction stores to consecutive memory only the elements whose corresponding input is "yes". We can then logically negate the yes/no values and apply the instruction again to write the elements to the other partition. This strategy has been used in an AVX-512-specific Quicksort. But what about other instruction sets such as AVX2 that don't have compress-store? Previous work has shown how to emulate this instruction using permute instructions.
> We build on these techniques to achieve the first vectorized Quicksort that is portable to six instruction sets across three architectures, and in fact outperforms prior architecture-specific sorts.
Vectorized and performance-portable Quicksort - https://news.ycombinator.com/item?id=31622548 - June 2022 (142 comments)
Would they do the same thing today or have an LLM re-implement those 3000 lines of c++ ?
I think software engineering in general is in a bit of a discoverability crisis. So many problems actually have solutions implemented... Somewhere. If you know about them. And are speaking the same vocabulary as the original implementer to realize the solution might be applicable to your problem. It's one of the reasons that jokes exist about microservice frameworks (https://www.youtube.com/watch?v=y8OnoxKotPQ) and how "We use Hadoop to store the output from our Kafka pipe, that's populated from our Traefik layer, all monitored with Grafana in front of Loki and Prometheus, of course" is a real sentence that has actual meaning and not a fever-dream.
LLMs are actually pretty impressive at being able to pull together disparate information from various domains into one place.
If you're curious why you would want a vectorized way to sort lists of numbers, one use case is building histograms - it's much easier to build a histogram if you've sorted all your samples first
Could AI be used this way? Just splat a visual representation of each item on a virtual wall and have an AI "visually" pick them out?
Only the likes of MAG 7, and a couple of hedge-funds would ask to do it since this problem directly applies to them.
But certainly not pre-revenue startups.