Dual-pivot quicksort (updated)

Published 2023-06-12

A while back I posted an implementation of an in-place dual-pivot quicksort, which is the default sort algorithm most standard libraries offer these days. I've since tweaked it a bit to save a few tokens, and today I wrote up a sample cart that does some primitive testing as an example of usage.

This includes both a general 221-token qsort(), which can accept a custom comparator function (defaults to a less-than comparator for ascending order), and a tweaked 199-token iqsort(), which inlines the comparisons as simple "<" operators, producing a smaller and faster sort in return for the sort order and index not being customizable.

See tab 0's header comment for more details.

(Side note: I realized while implementing comparators that you could sneak in shuffle functionality just by sorting with a random coin-flip comparator. Handy.)

Edit: WARNING! Do NOT grab the function from the "Code" flyout on the embedded cart below! There is a bug on the BBS right now that deletes a "<" comparison! Click the "Cart" button to download the .p8.png version!


Feel free to use it in any way you wish. I didn't invent the algorithm, and the implementation was inspired by looking at several other people's implementations (which in turn were inspired by other people's implementations, and so on). I'm not going to claim any original work here. I just did some grunt work tidying it up and applying ducktape where needed.

Please let me know ASAP if you find any bug. I think it's solid, but I know I'm not perfect.