What's the most efficient way to insert an element into a sorted vector?

Question

I have a sorted v: Vec<EventHandler<T>> and I want to insert an element into it while keeping it sorted. What's the most efficient way to do so? Rust doesn't seem to have a built-in way to do it.

EventHandler<T> is as follows:

struct EventHandler<T: Event + ?Sized> {
    priority: i32,
    f: fn(&mut T),
}

Because of how sorting works, inserting and sorting would be inefficient, with O(n log n) time complexity and 2*n allocation cost.

There are `binary_search` and `insert` methods implemented for Vec. So just find the proper index and insert your new element there. — Konstantin V. Salikhov, Mar 27 '16 at 16:34
@SoniEx2 I'm not sure why people down-voted it, but please add some code. This would name certain variables -- answers could easily refer to those names. You could also ask "What's the **best** [or **shortest**] way to...". — Lukas Kalbertodt, Mar 27 '16 at 18:11
This question is equivalent to "what's the most efficient way to hammer in nails with a screwdriver?". Inserting into the middle of the vector **requires** you to move all the subsequent items down, which will always be an O(n) operation. Use a datastructure that maintains the sorted nature. A [`BinaryHeap`](http://doc.rust-lang.org/std/collections/struct.BinaryHeap.html) is one possibility. — Shepmaster, Mar 27 '16 at 21:07
Related question about [inserting *multiple* items into the middle of a vector](http://stackoverflow.com/q/28678615/155423) — Shepmaster, Mar 28 '16 at 03:11

Lukas Kalbertodt · Accepted Answer · 2016-03-28T11:29:49.830

The task consists of two steps: finding the insert-position with binary_search and inserting with Vec::insert():

match v.binary_search(&new_elem) {
    Ok(pos) => {} // element already in vector @ `pos` 
    Err(pos) => v.insert(pos, new_elem),
}

If you want to allow duplicate elements in your vector and thus want to insert already existing elements, you can write it even shorter:

let pos = v.binary_search(&new_elem).unwrap_or_else(|e| e);
v.insert(pos, new_elem);

But: be aware that this has a runtime complexity of O(n). To insert into the middle, the vector has to move every element right of your insert-position one to the right.

So you shouldn't use it to insert more than a few elements into a vector, which isn't tiny in size. Particularly, you shouldn't use this method to sort a vector, as this insertion sort algorithm runs in O(n²).

A BinaryHeap might be a better choice in such a situation. Each insert (push) has a runtime complexity of just O(log n) instead of O(n). You can even convert it into a sorted Vec with into_sorted_vec(), if you so desire. You can also continue to use the heap instead of converting it.

The push has a time complexity of `O(N)`: `O(log N)` search + `O(N)` insertion. If you insert in reversed order, you have a time complexity of `O(N²)`, instead of `O(N log N)` of a binary heap. — Kijewski, May 23 '23 at 17:19

What's the most efficient way to insert an element into a sorted vector?

1 Answers1