i'm curious, in first place, why std::list , std::forward_list include sorting functions member functions, unlike every other standard library container. what's more interesting me both cppreference , cplusplus claim sorting done in o(n log n) time.
i can't imagine how 1 sort container without random access elements. threw test, using forward_list make difficult possible.
#include <chrono> #include <cstdint> #include <deque> #include <forward_list> #include <iostream> #include <random> 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<high_resolution_clock> start; time_point<high_resolution_clock> 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<nanoseconds>(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<nanoseconds>( current_time.time_since_epoch()).count(); random_generator.seed(nanos); return random_generator; } int main() { stopwatch timer; std::deque<length_of_time> times; auto generator = make_random_generator(); (int = 1; <= test_size; i++) { std::forward_list<uint64_t> container; (int j = 1; j <= i; j++) { container.push_front(generator()); } timer.start_timing(); container.sort(); timer.end_timing(); times.push_back(timer.get_elapsed_time()); container.clear(); } (const auto& time: times) { std::cout << time << endl; } } the numbers program output gave following graph:
which indeed o(n log n) growth (although spikes @ each third of way across interesting). how library this? perhaps copy container supports sorting, sort that, , copy back?
linked lists can sorted in o(n log n) using mergesort.
interestingly, since linked lists have appropriate structure, sorting linked list mergesort requires o(1) space.
the fact requires specialized algorithm tuned list structure reason sort member function of list, rather separate function.
as how works - need merge operation. merge operation takes 2 lists. @ heads of both lists, , remove smallest head , append result list. keep doing until heads have been merged big list - done.
here's sample merge operation in c++:
struct node { node* next; int val; }; node* merge(node* a, node* b) { node fake_head(nullptr, 0); node* cur = &fake_head; while (a && b) { if (a->val < b->val) { cur->next = a; = a->next; } else { cur->next = b; b = b->next; } cur = cur->next; } cur->next = ? : b; return fake_head.next; } 