orlp

glidesort

Rust2023–2026

orlp / glidesort

glidesort

A Rust implementation of Glidesort, my stable adaptive quicksort/mergesort hybrid sorting algorithm.

Libraries & SDKs

Explore on GitHub Read Hacker News discussions

4Distinct people

8Mentions

0Explicit recommenders

1.7KGitHub stars

REPOSITORY AT A GLANCE

What to know before exploring

What it is

A Rust implementation of Glidesort, my stable adaptive quicksort/mergesort hybrid sorting algorithm.

GitHub

Where it is used

No documented product use has been verified yet.

What people are saying

No recommendation phrase was found in the indexed comments.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

No other repository is repeatedly linked in the same discussions.

This week on Hacker News

Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 3:56:07 PM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by year8 dated mentions

Observed mentions: 2023-02-03 19:00:45 UTC to 2026-06-05 08:24:35 UTC.

* An incomplete calendar period is marked with an outlined bar. Its count is not directly comparable with a full period.

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges

UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
Period	Start (UTC)	End (exclusive, UTC)	Mentions	Submissions	Comments
2023	2023-01-01 00:00:00 UTC	2024-01-01 00:00:00 UTC	7	2	5
2024	2024-01-01 00:00:00 UTC	2025-01-01 00:00:00 UTC	0	0	0
2025	2025-01-01 00:00:00 UTC	2026-01-01 00:00:00 UTC	0	0	0
2026 (partial)	2026-01-01 00:00:00 UTC	2027-01-01 00:00:00 UTC	1	0	1

What Hacker News says

8 sources

orlp·Jun 5, 2026

It's called driftsort because it's derived from another sort I made, glidesort: https://github.com/orlp/glidesort. Glidesort is a bit faster still for large inputs, however it was too large and complex for inclusion in the standard library, and suffered from code size penalties on small inputs. So driftsort is a slimmed down version more appropriate for general purpose.

In Branchless Quicksort faster than std:sort and pdqsort with C and C++ API

killcoder·Mar 6, 2023

For context this is written by the creator of Glidesort: https://github.com/orlp/glidesort

In The Smallest Hash Table

todsacerdoti·Feb 10, 2023Submission

Orlp/glidesort: a Rust implementation of Glidesort, my stable adaptive quicksor

3 points · Open discussion

orlp·Feb 4, 2023

> It is my impression that orlp suggests the only relation between glidesort and fluxsort is that they're both stable quicksorts. So what is the relationship then, in your eyes? I implemented my own branchless partition operator that switches between overwriting / cmov'ing depending on data size (https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb...), my own bidirectional partitioning scheme, my own pivot selection scheme, my own low-cardinality scheme based on my prior work. As I wrote before "fluxsort's out-of-place stable partitioning. From this I got reminded that not only is out-of-place stable partitioning a thing, it's highly competitive". This is also what I credit on my page: "credit to Igor van den Hoven's fluxsort for demonstrating that stable quicksort can be efficient in practice". And glidesort isn't a quicksort, i

Read the rest

t is truly a hybrid. > Similarly, orlp suggests there is no relationship between his branchless merge and quadsort's branchless merge. I implemented it from scratch (10+ different versions), myself: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... You can still see artifacts of all the things I've tried there as well as in the select function: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... I was confident branchless merging could work efficiently. You could say quadsort contributed to the confidence it would work. But I did not use your branchless merge, period. > So he has no problem giving prior credit, but at least to me, it appears he tries to take prior or co-inventor claim for quadsort's branchless merge techniques and suggests a minimal influence from fluxsort. I will edit the readme to explicitly mention that glidesort's bidirectional merging is inspired by and an extension of quadsort's parity merge. But you didn't invent the branchless merge, and neither did I. We both came up with our own versions, both after the "Branch Mispredictions Don't Affect Mergesort" paper. > There is also no mention of the massive performance gain by utilizing the unguarded aspect of quadsort's parity merge for small array sorting. This is at least 20% of glidesort's performance gain. It's not 20%, at least on my machine. This optimization is precisely what the `--features unstable` flag enables, because this optimization is not sound to do for non-Copy types (and thus needs specialization in Rust). So it's easy to test, for me it's a 11% speedup over the branchless guarded merge: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb... Yes, I also made the guarded merge branchless. I don't believe quadsort does that, because it doesn't have to deal with elements that may not be copied. You can see the different selection of code based on specialization here: https://github.com/orlp/glidesort/blob/56cacab4e378e75ab6feb...

In Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data

orlp·Feb 3, 2023

> Is that done by further recursing merges for larger merge sizes? Yes. > Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space? Both. I haven't worked out the exact math yet, but it's likely something on the order of O(log (n / s)) recursive layers. > I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question If you are reading the code, the whole small-memory magic happens in physical_merge: https://github.com/orlp/glidesort/blob/master/src/physical_m.... Lines 46-59 are the large-enough memory happy path. Lines 60-65 is the low-memory path in-place recursive path. All other merge functions use try_merge_into_scratch as a happy path, and if that fails end up deferring to physical_merge.

In Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data

timerol·Feb 3, 2023

> How can it do merges in space (much) smaller than the input. That's part of it. More specifically I'm interested in the dynamic nature of the space overhead. In the video you linked, from 10 to 12 seconds, it looks like the algorithm is using about n/4 scratch space. But for larger arrays, it's bounded at n/8. Is that done by further recursing merges for larger merge sizes? Is the number of recursive layers needed to do a big merge determined by the size of the input, or the size of the scratch space? I see that try_merge_into_scratch will fail when the scratch space isn't big enough, which mostly answers my question https://github.com/orlp/glidesort/blob/master/src/physical_m.... But I'm still not sure how that failure causes the overall algorithm to change (I have been trying to ask about how glidesort uses the preallocated scratch sp

Read the rest

ace internally, not how it interfaces with system memory and system allocators.)

In Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data

orlp·Feb 3, 2023

> How does the algorithm stay bounded in memory usage? Is glidesort written in such a way to never use more memory than that? It does not ever allocate more than what it allocated at the start. > Is the some sort of back-pressure mechanism, when most of the allocated memory is in use, and another operation is ongoing? Yes and no. I did write some code that will make glidesort back off and use less memory if the allocation request fails: https://github.com/orlp/glidesort/blob/master/src/lib.rs#L20... The sad part is that this will probably never work in reality due to overcommit. > Basically: when sorting a 1 GiB array of data, how does the algorithm keep from using more than 128 MiB of additional memory? By allocating 128 MiB at the start, and never allocating more than that. Maybe what you really want to know is: how can it do merges in

Read the rest

space (much) smaller than the input? The answer is by (recursively) splitting merges into two separate smaller merges using an in-place block swap. You can see this in action at the 10 to 12 second mark here: https://user-images.githubusercontent.com/202547/216675278-e... Because I use block swaps and not rotations, this block swap can often be done implicitly (just not in the case of low-memory fallbacks) by re-assigning buffer names rather than physically moving elements.

In Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data

orlp·Feb 3, 2023Submission

Show HN: Glidesort, a new stable sort in Rust up to ~4x faster for random data

Hi all, I've talked about glidesort a few times on HN already, but it's finally ready for release. If you have any questions, feel free to ask. An academic paper on glidesort that goes into a lot more detail than the readme is upcoming, but is not ready yet. I will be giving a talk on glidesort tomorrow at FOSDEM 2023 in the Rust Devroom at 16:10, you can seek me out there as well. In other news, I am leaving academia soon, so if you have interesting (Rust) jobs the coming months feel free to approach me.

389 points · Open discussion