A Rust implementation of Android's Binder

Accidentally quadratic _worst case_ only. It's the Quick Select defect, essentially a defect in the core of Quick Sort which for the same reason impacts most C qsort implementations into the 1990s and made some C++ standard library implementations non-compliant (the ISO document eventually promised better performance for its unstable sort than is actually achievable with Quick Sort) long after that.

I was skimming an old (like 30+ years old) Fortran book last week which gives this problem as a reason why its authors don't like Quick Sort although they admit it's technically faster on average. Today of course that book's advice is obsolete, you should use (and later Rust's authors did here) an introsort or some other modern better sort which didn't exist when that Fortran book was written

Keeping everything in order is excellent except when that's the wrong order, hence select_nth_unstable_by takes a function for the ordering we want, which doesn't have to be (indeed usually won't be) the natural ordering of this type. The kernel does have a lot of gnarly intrusive linked lists, and for its purpose this really is sometimes, even often the Right Thing™ because it's doing tricky concurrency acrobatics for example - but since linked lists are also the go-to data structure for C programmers that's not a sure bet as to why there's a linked list, sometimes it just "Not bad enough to pick something else" and a Vec<T> or similar structure natural to a Rust programmer might be better.