title: How could a linked list achieve O(n log n) sorting time?
body: <p>I'm curious, in the first place, why <code>std::list</code> and <code>std::forward_list</code> include sorting functions as member functions, unlike every other standard library container. But what's more interesting to me is that both <a href="http://en.cppreference.com/w/cpp/container/forward_list/sort" rel="noreferrer">CPPReference</a> and <a href="http://www.cplusplus.com/reference/forward_list/forward_list/sort/" rel="noreferrer">CPlusPlus</a> claim that this sorting is done in O(<em>n</em> log <em>n</em>) time.</p>
  
  <p>I can't even imagine how one would sort a container without random access to elements. So I threw together a test, using <code>forward_list</code> to make it as difficult as possible.</p>
  
  <pre><code>#include &lt;chrono&gt;
  #include &lt;cstdint&gt;
  #include &lt;deque&gt;
  #include &lt;forward_list&gt;
  #include &lt;iostream&gt;
  #include &lt;random&gt;
  
  using std::endl;
  using namespace std::chrono;
  
  typedef nanoseconds::rep length_of_time;
  constexpr int TEST_SIZE = 25000;
  
  
  class Stopwatch
  {
      public:
          void start_timing();
          void end_timing();
          length_of_time get_elapsed_time() const;
      private:
          time_point&lt;high_resolution_clock&gt; start;
          time_point&lt;high_resolution_clock&gt; end;
          length_of_time elapsed_time = 0;
  };
  
  
  void Stopwatch::start_timing()
  {
      start = high_resolution_clock::now();
  }
  
  
  void Stopwatch::end_timing()
  {
      end = high_resolution_clock::now();
      auto elapsed = end - start;
      auto elapsed_nanoseconds = duration_cast&lt;nanoseconds&gt;(elapsed);
      elapsed_time = elapsed_nanoseconds.count();
  }
  
  
  length_of_time Stopwatch::get_elapsed_time() const
  {
      return elapsed_time;
  }
  
  
  std::mt19937_64 make_random_generator()
  {
      using namespace std::chrono;
      auto random_generator = std::mt19937_64();
      auto current_time = high_resolution_clock::now();
      auto nanos = duration_cast&lt;nanoseconds&gt;(
              current_time.time_since_epoch()).count();
      random_generator.seed(nanos);
      return random_generator;
  }
  
  
  int main()
  {
      Stopwatch timer;
      std::deque&lt;length_of_time&gt; times;
      auto generator = make_random_generator();
      for (int i = 1; i &lt;= TEST_SIZE; i++) {
          std::forward_list&lt;uint64_t&gt; container;
          for (int j = 1; j &lt;= i; j++) {
              container.push_front(generator());
          }
          timer.start_timing();
          container.sort();
          timer.end_timing();
          times.push_back(timer.get_elapsed_time());
          container.clear();
      }
  
      for (const auto&amp; time: times) {
          std::cout &lt;&lt; time &lt;&lt; endl;
      }
  }
  </code></pre>
  
  <p>The numbers this program output gave the following graph:</p>
  
  <p><img src="https://i.stack.imgur.com/fWNPV.png" alt="forward list sorting time"></p>
  
  <p>Which does indeed look like O(<em>n</em> log <em>n</em>) growth (although the spikes at each third of the way across are interesting). How does the library do this? Perhaps copy to a container that supports sorting, sort that, and copy back?</p>