ACP: Add a `partial_sort` method to `[T]`

[tisonkun]

Proposal

Problem statement

[T] now has:

• sort
• sort_by
• sort_unstable
• sort_unstable_by

In my scenario to implement a "Top-N" algorithm over slices, it'd be better to have a partial_sort analogy to the sort family.

See the alternative and links for the existing workaround and discussions.

Motivating examples or use cases

impl<T> [T] {
  // `n` is the length of the sorted slice
  pub fn partial_sort(&mut self, n: usize) where T: Ord { ... }
  pub fn partial_sort_by<F>(&mut self, n: usize, mut compare: F) where F: FnMut(&T, &T) -> Ordering { ... }
  pub fn partial_sort_unstable(&mut self, n: usize) where T: Ord { ... }
  pub fn partial_sort_unstable_by<F>(&mut self, n: usize, mut compare: F) where F: FnMut(&T, &T) -> Ordering { ... }
}

#[test]
fn demostration() {
    let mut before: Vec<u32> = vec![4, 4, 3, 3, 1, 1, 2, 2];
    let last = 6;
    let mut d = before.clone();
    d.sort();

    before.partial_sort_by(last, |a, b| a.cmp(b));
    assert_eq!(&d[0..last], &before[0..last]);
}

Solution sketch

arrow-ord provides an implementation:

/// It's unstable_sort, may not preserve the order of equal elements
pub fn partial_sort<T, F>(v: &mut [T], limit: usize, mut is_less: F)
where
    F: FnMut(&T, &T) -> Ordering,
{
    if let Some(n) = limit.checked_sub(1) {
        let (before, _mid, _after) = v.select_nth_unstable_by(n, &mut is_less);
        before.sort_unstable_by(is_less);
    }
}

We can start from here and further internal improvement.

Alternatives

There is an existing crate for partial_sort: https://github.com/sundy-li/partial_sort

... and I'm currently using it in ScopeDB, where it works well.

Links and related work

• https://en.cppreference.com/w/cpp/algorithm/partial_sort.html
• [ER] slice::partial_sort ? rust#94256

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[kennytm]

I noticed that there is no stable version of select_nth, and C++ does not provide a std::partial_stable_sort either, so I wonder if there is actually an efficient way (O(1) space (in-place) + O(N log M) time) to perform the stable partial_sort/partial_sort_by.

[tisonkun]

I noticed that there is no stable version of select_nth, and C++ does not provide a std::partial_stable_sort either, so I wonder if there is actually an efficient way (O(1) space (in-place) + O(N log M) time) to perform the stable partial_sort/partial_sort_by.

In case we have only the unstable version, shall we name it partial_sort_unstable or can it be partial_sort?

[kennytm]

since we only have select_nth_unstable I think it should better be also partial_sort_unstable

[scottmcm]

The select_nth_unstable+sort_unstable approach seems asymptotically optimal, and probably surprisingly good since the select will leave things more-sorted already, which the partition-based unstable sort will likely to take advantage of it. I don't know if there's a good stable way to do this, other than the by_cached_key approach of sorting (usize, &T) then applying the permutation.

Note that there's https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.k_smallest that can work really well for this since you don't need the whole thing in a single slice -- you can use O(k) space instead of O(n).

What were you hoping to do with this method? Something like TOP K in a DB feels like you wouldn't want to load everything into a Vec in the first place.

[tisonkun]

Note that there's https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.k_smallest that can work really well for this since you don't need the whole thing in a single slice -- you can use O(k) space instead of O(n).

Good to know. This is a good alternative to use.

What were you hoping to do with this method? Something like TOP K in a DB feels like you wouldn't want to load everything into a Vec in the first place.

Not everything. Just as part of the partial sort executor implementation. Partial sort is a generic requirement, though.

Different from k_smallest, this is an in-place modifier.

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting and we're happy to add these, but we would like a second opinion from the authors of the current sort algorithm in the standard library (cc @orlp @Voultapher). In particular, does it make sense to have both a stable and unstable version of this?

[quaternic]

The proposed API only allows for sorting a prefix of a slice. If you want the greatest elements to the end of the slice, it wouldn't help. Would it make sense to take a range for which items should be in sorted order?

Then instead of v.partial_sort_unstable(n), you'd write v.partial_sort_unstable(0..n), where its also clearer why v[n] will not be in sorted order. That is, the bare usize could plausibly be an inclusive index, but the exclusive end of a range surely isn't.

Actually, that starts to look a lot like a generalized select_nth_unstable where the index can also be a range. The return value could similarly be a tuple of slices: (before, sorted, after).

---

C++'s partial_sort works with (random access) iterators so a suffix can be sorted with reverse iterators, though you also have to flip the comparator:

std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});

Also, https://en.cppreference.com/w/cpp/algorithm/partial_sort.html#Notes states that

std::partial_sort algorithms are intended to be used for small constant numbers of [first, middle) selected elements.

To me that looks like one reason it exists as a separate thing instead of just "use nth_element and then sort the prefix".

[orlp]

@Amanieu Partial sorting pretty much precludes bottom-up methods like mergesort, so you'd be looking at a top-down method like quicksort. For most standard libraries that would be the end of the story as they don't have a stable quicksort nor would it be worth implementing one for this purpose, but we do already have a stable quicksort.

I personally don't see any reason why you would want to do a partial stable sort, but at least algorithmically I believe it's simply taking our (stable) quicksort and stopping the recursion whenever a partition completely falls outside the to-be-sorted range.

[Amanieu]

In that case, I think it makes sense to only accept partial_sort_unstable for now. We can re-consider the stable variant if there turns out to be demand for it.

Please open a tracking issue and open a PR to rust-lang/rust to add it as an unstable feature. You can close this ACP once the tracking issue has been created.

[orlp]

My suggestion would be to accept a range a..b after which it's guaranteed that:

• Every element in the range ..a is smaller than or equal to
• every element in the range a..b, which is sorted and smaller than or equal to
• every element in b...

[Amanieu]

@orlp Interesting! Would this also allow partial_sort to work as a partitioning algorithm by specifying a zero-sized range? Or would we still want a specialized algorithm for that?

[quaternic]

Well, sort of, though it's not the classic partitioning as used in quicksort: Iterator::partition_in_place (in nightly since 2019) looks at each element precisely once to create partitions {x s.t. f(x)} and {x s.t. !f(x)}, meaning the lengths are only known when it's done.

v.partial_sort_unstable(a..a) needs to do additional work to produce partitions with lengths a and len - a exactly.
Probably still useful for some situations.