title: Which is faster, sorting a vector, then putting it into an AVL tree, or inputting it directly?
body: <p>So here's the situation:</p>
  
  <p>I have millions, possibly billions, of strings that I am trying to parse and put into a sorted structure, lets say I have 5,000,000 strings.
  I'm trying to write a fast program that can put all of these strings from an unsorted vector into an ordered data structure that can also search the structure fast, thus the reasoning for the AVL tree (which eventually I plan to use a hash table of a-z for even faster lookup, but that comes later). I get all of the strings into a vector first, but they are all jumbled up, unsorted and different lengths. 
  I don't want any repeated strings in my tree, so if the program finds the strings "hello" and "hello" it would only have one AVL entry and would  increment an integer holder for the frequency that this string has appeared. </p>
  
  <p>So my question is this: would it be faster to sort the vector first (using something fast like a multi-threaded quicksort or something else) and then input it into the AVL tree, after all the words are sorted together with other same words, OR is it faster to just put all the data from the unsorted vector into the AVL tree, and continously checking the AVL tree for whether or not a word already exists, then incrementing it.</p>
  
  <p>So to picture it in an order of operations here are the two cases:</p>
  
  <pre><code>CASE A:
  
  &gt; Get input/parse strings
  &gt; Put strings into vector (unsorted)
  &gt; Put vector into array or linked-list
  &gt; Quicksort that array/llist
  &gt; Input that sorted array into the AVL Tree
  </code></pre>
  
  <p></p>
  
  <pre><code>CASE B:
  
  &gt; Get input/parse strings
  &gt; Put strings into vector (unsorted)
  &gt; Insert vector data into AVL tree
  &gt; During insertion, check if there are duplicate words, if so, increment the counter
  </code></pre>
  
  <p>
  Which case is faster??</p>
  
  <p><strong>--EDIT--</strong> So after hearing some of the comments, inserting a sorted array into an AVL tree from the beginning would be a bad idea, which makes sense due to how many rotations would be made. It seems that directly inserting into the AVL tree is probably a good idea, but what is the best way to efficiently insert when a word is already in the tree somewhere? How can I make sure that I find it? Is that where my sorting can come in?</p>