title: Insertion Sort Optimization
body: <p>I'm trying to practice making some different sort functions and the insertion function that I came up with is giving me some trouble. I can sort lists that are less than 30K fairly quickly. But I have a list of 100K integers and it literally takes 15 minutes for the function to complete the sort. Everything is sorted correctly, but I don't believe it should take that long. </p>
  
  <p>Am I missing something with my code that is making it take so long? Many thanks in advance. </p>
  
  <pre><code>void Sort::insertion_Sort(vector &lt;int&gt; v)
  {
      int vecSize = v.size(); 
  
      //for loop to advance through the vector
      for (int i=0; i &lt; vecSize; i++)
      {
          //delcare some variables 
          int cursor = i; 
          int inputCursor = i-1; 
          int temp = v[cursor]; 
  
          //check to see if we are considering only a single element 
          if (cursor &gt; 0)
          {
              //if there is more than 1 element, then we test the following. 
              //1. is the cursor element less than the inputCursor(which 
              //is the previous element) 
              //2. is the input cursor greater than -1
              while (inputCursor &gt; -1 &amp;&amp; v[cursor] &lt; v[inputCursor] )
              {
  
                      //if so, we swap the variables 
                      //then move the cursors back to check 
                      //the previous elment and see if we  need to swap again. 
                      temp = v[cursor];
                      v[cursor] = v[inputCursor];
                      v[inputCursor] = temp;
                      inputCursor--;
                      cursor--; 
              }
          }
      }
  }
  </code></pre>