title: What makes the gcc std::list sort implementation so fast?
body: <p>I have a linked list implementation and I'm experimenting with both Mergesort and QuickSort algorithms.</p>
  
  <p>What I don't understand is why the sort operation in std::list is so fast.
  Looking at the std::list under linux and it appears to be linked list as well, not an array based list.</p>
  
  <p>The merge sort I tried almost identical to Dave Gamble's version here:
  <a href="https://stackoverflow.com/questions/7685/merge-sort-a-linked-list">Merge Sort a Linked List</a></p>
  
  <p>Also, I thought I'd try a simple quicksort based on this code:
  <a href="http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml" rel="nofollow noreferrer">http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml</a></p>
  
  <p>Suprisingly, to sort 10 million random numbers using std::list and sort was around 10 times quicker than either of those others.  </p>
  
  <p>And for those that are asking, yes I need to use my own list class for this project.</p>