title: Improving run time complexity of insert sort?
body: <p>I've written the following code to try to perform an insert into a sorted vector in O(log n) run-time:</p>
  
  <pre><code>std::vector&lt;int&gt; to_insert_sort {2,3,5,6,1,1,3,2};
  
  int to_insert {3};
  
  std::sort(to_insert_sort.begin(), to_insert_sort.end()); //O(log n)
  
  auto pos = std::upper_bound(to_insert_sort.begin(), to_insert_sort.end(), 5); //O(log n)
  
  to_insert_sort.insert(pos, to_insert); //O(n)
  </code></pre>
  
  <p>1) Am I right in saying this operation is O(log n)?</p>
  
  <p>2) Are there ways of performing this operation with increased run-time efficiency? </p>