2_4.cpp

/*
Time: O(N)
Space: O(N)
*/
template <typename T>
list<T> sort(list<T> &li,const T &x){
    list<T> less;
    list<T> more;
    typename list<T>::iterator i;
    for ( i = li.begin(); i != li.end(); i++ ){
        if (*i < x){
            less.push_back(*i);
        }
        else{
            more.push_back(*i);
        }
    }
    less.splice(less.end(),more);
    return less;
}