How can a list be sorted?

To sort a list in C++, you can use the following approaches:

1. std::sort: An iterative algorithm from the standard library.
2. std::list::sort: A sorting method for std::list, which uses references to elements rather than iterators.

Comparison:

Method	Applies to	Complexity	Additional memory	Stability	Features
std::sort	Random access (e.g., std::vector, std::deque)	$O(N \log N)$	$O(\log N)$ (average)	Unstable	Not efficient for std::list due to slow random access.
std::list::sort	std::list	$O(N \log N)$	$O(1)$	Stable	Efficient for std::list, as it does not require moving elements.

Example of using std::list::sort:

#include <list>
#include <iostream>

int main() {
    std::list<int> my_list = {5, 2, 8, 1, 9};
    
    // Sort in ascending order
    my_list.sort();
    
    for (int val : my_list) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Sort in descending order using a comparator
    my_list.sort([](int a, int b){ return a > b; }); 

    for (int val : my_list) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}