Как отсортировать данный шаблонный двусвязный класс?

#include <iostream>
#include <string>
#include <cstdlib>
 
 
// базовый класс элемента связного списка
// не содержит данных, содержит часть логики
struct NodeBase {
    NodeBase *prev; // указатель на предыдущий элемент связного списка
    NodeBase *next; // указатель на следующий элемент связного списка
                    // при создании объекта класса конструктор по-умолчанию
                    // назначает следующий и предыдущий элемент указывать на себя 
    NodeBase() : prev(this), next(this) {}
    // при создании с таким констуктором, элемент добавляет сам себя
    // в связный список, представляя себя предыдущему и следующему элементу
    NodeBase(NodeBase *prev_, NodeBase *next_)
        : prev(prev_), next(next_) { // назначаются предыдущий и следующий элементы
                                     // у предыдущего элемента следующим элементом назначается данный элемент
                                     // и у следующего элемента предыдущим элементом назначается данный элемент
        prev->next = next->prev = this;
    }
    // деструктор. при удалении элемента связного списка, 
    // элемент убирает сам себя из списка
    virtual ~NodeBase() {
        prev->next = next;
        next->prev = prev;
    }
};
 
// элемент связного списка, уже содержащий данные.
template <typename ValueType>
struct Node : public NodeBase {
    ValueType value; // то значение, которое хранит класс
                     // конструктор подставляет значения и вызывает конструтор предка
    Node(NodeBase *prev_, NodeBase *next_, ValueType value)
        : NodeBase(prev_, next_), value(value) {}
};
 
// итератор. класс, который позволит получать доступ к данным,
// сохранив инкапсуляцию
template <typename ValueType>
struct Iterator {
private:
    // собственно, элемент связного списка, который хранит итератор
    NodeBase *node;
public:
    // создание итератора при помощи элемента связного списка
    explicit Iterator(NodeBase *node_) : node(node_) {}
    // создание копированием с другого итератора
    Iterator(const Iterator &other) : node(other.node) {}
    // получение значения элемента связного списка
    ValueType &operator*() {
        return static_cast<Node<ValueType>*>(node)->value;
    }
    // присваивание итератору другого итератора
    Iterator &operator=(const Iterator &other) {
        if (&other != this)
            node = other.node;
        return *this;
    }
    // переход к следующему элементу (постфиксный)
    Iterator &operator++() {
        node = node->next;
        return *this;
    }
    // переход к предыдущему элементу (постфиксный)
    Iterator &operator--() {
        node = node->prev;
        return *this;
    }
    // проверка итераторов на равенство
    bool operator==(const Iterator &other) {
        return node == other.node;
    }
    // ... на неравенство
    bool operator!=(const Iterator &other) {
        return node != other.node;
    }
 
};
 
// собственно, шаблон двусвязного списка
// смотрите, как мало собственно кода, если убрать комментарии
template <typename ValueType>
class List {
private:
    // базовый эелемент.
    // его поле next указывает на первый элемент списка
    // поле prev указываеты на последний элемент списка
    // если список пуст, next == prev == &base
    NodeBase base;
public:
    // конструктору по-умолчанию делать в принципе нечего, он должен быть объявлен
    List() : base() {};
    // деструктор удаляет список функцией Clear
    ~List() {
        Clear();
    }
    // функция проверяет, пустой ли список
    bool Empty() {
        // список пустой, если базовый элемент указывает сам на себя
        return ((base.next == &base) && (base.prev == &base));
    }
    void Clear() {
        // пока список не пуст
        while (!Empty())
            // удаляется первый элемент
            // работу по удалению из списка сделает деструктор класса элемента
            delete base.next;
    }
    // добавление элемента в конец списка
    void PushBack(const ValueType &value) {
        // просто создается новый элемент списка,
        // всё остальное сделает конструктор класса NodeBase
        new Node<ValueType>(base.prev, &base, value);
    }
    // удаление последнего элемента
    void PopBack() {
        // удаляется элемент связного списка 
        // (в данном случае последний, но в принципе, сработает с любым)
        // работу по фактическому удалению элемента из списка выполнит деструктор
        // класса NodeBase
        delete base.prev;
    }
    // плохой стиль, лучше делать через итераторы, но эта концепция, наверно,
    // слишком сложна
    void PrintAll() {
        // перебор всех элементов в одном цикле
        for (NodeBase *node = base.next; node != &base; node = node->next)
            // для получения значения элемент списка приводится к типу Node*
            std::cout << static_cast< Node<ValueType>* >(node)->value;
    }
    // печать данных по условию
    template <class Predicate> // класс или функция, принимающие параметром
                               // ValueType и возвращающая true или false.
    void PrintIf(Predicate condition) {
        // цикл по всем элементам массива
        for (NodeBase *node = base.next; node != &base; node = node->next)
            // если условие выполняется
            if (condition(static_cast<Node<ValueType>*>(node)->value))
                // вывести значение
                std::cout << static_cast<Node<ValueType>*>(node)->value;
    }
    // итератор на начало связного списка
    Iterator<ValueType> Begin() {
        // началом связного списка является элемент, на который указывает
        // поле next переменной base
        return Iterator<ValueType>(base.next);
    }
    // итератор на элемент связного списка _после_ последнего
    Iterator<ValueType> End() {
        // элементом за связным списком является само поле base
        return Iterator<ValueType>(&base);
    }
    // поиск элемента в списке
    // принимает параметрами первый элемент и последний элемент, в
    // которых надо искать список
    // и функтор, принимающий значение элемента и возвращающая true или
    // false
    // возвращает итератор найденного элемента или последний параметр
    // если элемента не найдено
    template <class Predicate>
    Iterator<ValueType> Search(Iterator<ValueType> begin,
        Iterator<ValueType> end,
        Predicate condition) {
        for (; begin != end; ++begin)
            if (condition(*begin)) break;
        return begin;
    }
 
};
 
// класс человек
struct Person {
    std::string surname;
    std::string name;
    std::string otch;
    int phone;
    int date[3];
    
    
    Person(std::string surname_, std::string name_, std::string otch_,  int phone_, int date_[3])
        : surname(surname_), name(name_), otch(otch_), phone(phone_) {
        date[0] = date_[0];
        date[1] = date_[1];
        date[2] = date_[2];
    }  // переопределенный оператор для вывода на экран
    
    friend std::ostream& operator<<(std::ostream &stream, const Person &person) {
        return stream << 
             " Surname: " << person.surname
            << ", Name: " << person.name
            << ", Otch: " << person.otch
            << ", Phone : " << person.number
            << ", Date: " << person.date[0]<<'.'<<person.date[1] << '.' << person.date[2] 
            << std::endl;
    }
    // класс-функтор для поиска 
    struct IsPhone {
        // запоминаем параметр в классе
        IsPhone(int parameter_) : parameter(parameter_) {}
        // оператор-функтор для сравнения параметра
        bool operator()(const Person &person) {
            return person.phone == parameter;
        }
        int parameter; // параметр
    };
 
    // класс-функтор для поиска по дате рождения
    struct IsDate {
        // запоминаем параметр в классе
        IsDate(int parameter_[3]) 
        {
            for (int i = 0; i < 3; i++)
                parameter[i] = parameter_[i];
        }
        // оператор-функтор для сравнения параметра
        bool operator()(const Person &person) {
            if (person.date[0] == parameter[0] && person.date[1] == parameter[1] && person.date[2] == parameter[2])
                return true;
                else return false;
        }
        int parameter[3]; // параметр
    };
 
    // класс-функтор для поиска 
    struct IsSurname {
        // запоминаем параметр в классе
        IsSurname(const std::string &parameter_) : parameter(parameter_) {}
        // оператор-функтор для сравнения параметра
        bool operator()(const Person &person) {
            return person.surname == parameter;
        }
        std::string parameter; // параметр
    };
 
    struct IsName {
        // запоминаем параметр в классе
        IsName(const std::string &parameter_) : parameter(parameter_) {}
        // оператор-функтор для сравнения параметра
        bool operator()(const Person &person) {
            return person.name == parameter;
        }
        std::string parameter; // параметр
    };
 
};
 
int main(int argc, char *argv[]) {
    
    List<Person> a; 
        
    int n = 0;
    while (!0)
    {
        std::cout << "\n Menu \n\
1) New person \n\
2) Print notebook \n\
3) Search\n\
4) Sorting \n\
5) Delete \n\
0) Exit\n";
        std::cin >> n;
        if (n == 1) {
            std::string surname, name, otch;
            int nomer, date[3];
                        std::cout << "Surname... ";
            std::cin >> surname;
            std::cout << "Name... ";
            std::cin >> name;
            std::cout << "otch... ";
            std::cin >> otch;
            std::cout << "Nom... ";
            std::cin >> nomer;
            std::cout << "Date... ";
            for (int i=0;i<3;i++)
            std::cin >> date[i];
                    
            a.PushBack(Person(surname, name, otch, nomer, date));
        }
        if (n == 2) a.PrintAll();
        
        if (n == 3) {
            std::cout << "\nSearch\n\
            1) by Surname\n\
            2) by Name\n\
            3) by Phone\n\
            4) by birthday\n\
            0) Exit\n";
            int n2;
            std::cin >> n2;
            if (n2 == 1)
            {   std::string req;
                std::cin >> req;
                Iterator<Person> b = a.Search(a.Begin(), a.End(), Person::IsSurname(req));
                if (b != a.End())
                    std::cout << *b;
            }
 
            if (n2 == 2)
            {   std::string req;
            std::cin >> req;
            Iterator<Person> b = a.Search(a.Begin(), a.End(), Person::IsName(req));
            if (b != a.End())
                std::cout << *b;
            }
            
            if (n2 == 3)
            {   int req;
                std::cin >> req;
                Iterator<Person> b = a.Search(a.Begin(), a.End(), Person::IsPhone(req));
                if (b != a.End())
                    std::cout << *b;
            }
 
            if (n2 == 4)
            {   int req[3];
            std::cout << "Date... ";
            for (int i = 0; i<3; i++)
                std::cin >> req[i];
                Iterator<Person> b = a.Search(a.Begin(), a.End(), Person::IsDate(req));
                if (b != a.End())
                    std::cout << *b;
            }
 
            
        }
            
        if (n == 4) {
         
        }
        /*
        if (n == 0) {
            mybook.saveFile("struct.txt");
            return 0;
        }
        */
    }
    system("pause");
    return 0;
}

#include <iostream>
#include <cstdlib>
#include <ctime>
 
typedef struct Node
{    
    int data;
    Node *next;
} *PNode;
 
void push_front( PNode &head, int data )
{
    head = new Node { data, head };
}
 
std::ostream & display( const PNode &head, std::ostream &os = std::cout )
{
    for ( PNode current = head; current; current = current->next )
    {
        os << current->data << ' ';
    }
    return os;
}
 
void SortedInsert( PNode &head, PNode node )
{
    if ( !head || node->data < head->data )
    {
        node->next = head;
        head = node;
    }
    else
    {
        PNode current = head;
        while ( current->next && !( node->data < current->next->data ) )
        {
            current = current->next;
        }
 
        node->next = current->next;
        current->next = node;
    }
}
 
PNode InsertionSort( PNode &head )
{
    PNode result = nullptr;
 
    while ( head )
    {
        PNode node = head;
        head = head->next;
        SortedInsert( result, node );
    }
 
    return result;
}
 
int main() 
{
    const size_t N = 10;
    PNode head = nullptr;
 
    std::srand( ( unsigned int )std::time( nullptr ) );
 
    for ( size_t i = 0; i < N; i++ ) push_front( head, std::rand() % N );
 
    display( head ) << std::endl;    
 
    PNode head2 = InsertionSort( head );
 
    display( head2 ) << std::endl;    
 
    return 0;
}