title: An efficient sorting algorithm for almost sorted list containing time data?
body: <p>The name says it all really.  I suspect that insertion sort is best, since it's the best sort for mostly-sorted data in general.  However, since I know more about the data there is a chance there are other sorts woth looking at.  So the other relevant pieces of information are:</p>
  
  <p>1) this is time data, which means I presumable could create an effective hash for ordering of data.
  2) The data won't all exist at one time.  instead I'll be reading in records which may contain a single vector, or dozen or hundreds of vectors.  I want to output all time within a 5 second window.  So it's possible that a sort that does the sorting as I insert the data would be a better option.
  3) memory is not a big issue, but CPU speed is as this may be a bottleneck of the system.</p>
  
  <p>Given these conditions can anyone suggest an algorithm that may be worth considering in addition to insertion sort?  Also, How does one defined 'mostly sorted' to decide what is a good sort option?  What I mean by that is how do I look at my data and decided 'this isn't as sorted as I thought it as, maybe insertion sort is no longer the best option'?  Any link to an article which considered process complexity which better defines the complexity relative to the degree data is sorted would be appreciated.</p>
  
  <p>Thanks</p>
  
  <p>Edit:
  thank you everyone for your information.  I will be going with an easy insertion or merge sort (whichever I have already pre-written) for now.  However, I'll be trying some of the other methods once were closer to the optimization phase (since they take more effort to implement).  I appreciate the help</p>