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

by

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.

Leave a Comment