Como se pode ordenar uma lista?

Para ordenar uma lista em C++, pode usar as seguintes abordagens:

1. std::sort: Algoritmo iterativo da biblioteca padrão.
2. std::list::sort: Método de ordenação para std::list, que usa referências aos elementos em vez de iteradores.

Comparação:

Método	Aplica-se a	Complexidade	Memória adicional	Estabilidade	Características
std::sort	Acesso aleatório (por exemplo, std::vector, std::deque)	$O(N \log N)$	$O(\log N)$ (em média)	Não estável	Para std::list, ineficiente devido ao acesso aleatório lento.
std::list::sort	std::list	$O(N \log N)$	$O(1)$	Estável	Eficiente para std::list, pois não requer mover elementos.

Exemplo de uso de std::list::sort:

#include <list>
#include <iostream>

int main() {
    std::list<int> minha_lista = {5, 2, 8, 1, 9};
    
    // Ordenar em ordem crescente
    minha_lista.sort();
    
    for (int val : minha_lista) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    // Ordenar em ordem decrescente usando um comparador
    minha_lista.sort([](int a, int b){ return a > b; }); 

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

    return 0;
}