# Add a "Vec.sorted()" function

**URL:** <https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948>\
**Category:** Uncategorized\
**Created:** [March 9, 2020, 8:33pm UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948 "2020-03-09T20:33:33Z")\
**Posts on this page:** 8\
**Page:** 2

<div class="post-metadata">

**Author:** ![PoignardAzur](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/poignardazur/32/6464_2.png) [@PoignardAzur](https://internals.rust-lang.org/u/PoignardAzur)\
**Post date:** [March 13, 2020, 4:20pm UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948/21 "2020-03-13T16:20:33Z")

</div>

Doesn't that have wildly different performance characteristics?

I'd expect `.collect<BTreeSet<_>>()` to be terrible for cache locality, since it allocates a node for every element in your array.

---

<div class="post-metadata">

**Author:** ![RustyYato](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rustyyato/32/13627_2.png) [@RustyYato](https://internals.rust-lang.org/u/RustyYato)\
**Post date:** [March 13, 2020, 4:47pm UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948/22 "2020-03-13T16:47:26Z")

</div>

`BTreeSet` doesn't allocate nodes per value, but for some array of values, so it's not bad for the cache. Yes, a `Vec<_>` is better, but in this case I don't think it would be too bad.

From the [`BTreeMap`](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html) docs (`BTreeSet<T>` is a thin wrapper around `BTreeMap<T, ()>`)

> A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing this, we reduce the number of allocations by a factor of B, and improve cache efficiency in searches.

---

<div class="post-metadata">

**Author:** ![Aloso](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/aloso/32/5039_2.png) [@Aloso](https://internals.rust-lang.org/u/Aloso)\
**Post date:** [March 13, 2020, 6:38pm UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948/23 "2020-03-13T18:38:09Z")

</div>

Also, a `BTreeSet` can't be trivially converted to sorted slice. So there are use cases where `Vec.sorted()` is strictly better.

---

<div class="post-metadata">

**Author:** ![kornel](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kornel/32/2711_2.png) [@kornel](https://internals.rust-lang.org/u/kornel)\
**Post date:** [March 13, 2020, 8:46pm UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948/24 "2020-03-13T20:46:37Z")

</div>

Theoretically an iterator adapter could be slightly better by first incrementally quicksort-partitioning incoming elements, but OTOH it wouldn't be able to pick a good pivot element, so that partitioning may be terrible. So in the end, perhaps `.sorted()` just on the `Vec` is not too bad.

---

<div class="post-metadata">

**Author:** ![kornel](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/kornel/32/2711_2.png) [@kornel](https://internals.rust-lang.org/u/kornel)\
**Post date:** [March 13, 2020, 8:52pm UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948/25 "2020-03-13T20:52:45Z")

</div>

In [https://lib.rs](https://lib.rs) codebase I use this pattern quite often:

```rust
let mut tmp: Vec<_> = iter.collect();
tmp.sort_by(compare_floats);
tmp.truncate(10);

```

Theoretically for top-N sorted elements it's possible to optimize the sort and avoid most of the work on discarded elements. Rust currently doesn't have anything for this.

Maybe there could also be `.sorted_and_truncated(n)`? Or if `sorted()` was an iterator itself, then magically specialized `sorted().take(n)` would be awesome.

---

<div class="post-metadata">

**Author:** ![matklad](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/matklad/32/12266_2.png) [@matklad](https://internals.rust-lang.org/u/matklad)\
**Post date:** [March 13, 2020, 9:07pm UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948/26 "2020-03-13T21:07:40Z")

</div>

You can do lazy quick sort to achieve O(N) complexity here, but a faster solution is to do one pass with a binary heap of fixed size. This would look like this:

```rust
let mut top = BoundedBinaryHeap::new(10);
top.extend(iter):
top.into_sorted_vec()

```

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [March 14, 2020, 12:15am UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948/27 "2020-03-14T00:15:56Z")

</div>

> [@kornel](#):
>
> Theoretically for top-N sorted elements it's possible to optimize the sort and avoid most of the work on discarded elements. Rust currently doesn't have anything for this.

One way to get first-k-of-n in `O(n + k log(n))` is to use `BinaryHeap::from(the_vec).into_sorted_iter()`, since [that from is O(n)](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html#impl-From%3CVec%3CT%3E%3E). (I don't remember if `into_sorted_iter()` actually got added; if not then it's `iter::from_fn(|| the_heap.pop())`.)

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [June 12, 2020, 12:15am UTC](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948/28 "2020-06-12T00:15:58Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.

[Previous page](https://internals.rust-lang.org/t/add-a-vec-sorted-function/11948.md?page=1)