Сортировка в двусвязном списке

template <typename T>
void List <T>::sort()
{
    Node <T>* left = head;                
    Node <T>* right = head->pNext;          
 
    Node <T>* temp = new Node<T>;              
    while (left->pNext) {                 
        while (right) {
            for (size_t i = 0; i < lst.GetSize(); i++) {
                if ((left->lst[i]) < (right->lst[i])) {   
                    temp->lst[i] = left->lst[i];          
                    left->lst[i] = right->lst[i];           
                    right->lst[i] = temp->lst[i];         
                }
                right = right->pNext;                  
            }
        }
        left = left->pNext;                             
        right = left->pNext;                            
    }
}

#include <iostream>
#include <windows.h>
#include <iomanip>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
template <typename T>
class List
{
public:
 
    //Длина списка
    int GetSize() { return Size; }
 
    //Очистить список
    void clear();
 
    //Добавить элемент в начало списка
    void push_front(T data);
 
    //Добавить элемент в конец списка
    void push_back(T data);
 
    //Удалить элемент из начала списка
    void pop_front();
 
    //Удалить элемент из конца списка
    void pop_back();
 
    //Добавить элемент по указанному индексу
    void insert(T data, int index);
 
    //Удалить элемент по указанному индексу
    void removeAt(int index);
 
    T& operator [] (const int index);
 
    //Вывести список на экран
    void ShowData();
 
    //Сортировка
    void sort();
 
    
    List <T>();
    ~List <T>();
 
private:
 
    template <typename T>
    class Node
    {
    public:
        Node(T data = T(), Node* pNext = nullptr, Node* pPrev = nullptr)
        {
            this->data = data;
            this->pNext = pNext;
            this->pPrev = pPrev;
        }
 
        T data;
        Node* pNext;
        Node* pPrev;
    };
 
    Node <T>* head;
    Node <T>* tail;
    int Size;
 
};
 
 
List <int> lst;
template <typename T> List <T>::List()
{
    head = nullptr;
    tail = nullptr;
    Size = 0;
}
 
template <typename T> List <T>::~List()
{
    clear();
}
 
template<typename T>
void List<T>::clear()
{
    while (Size)
    {
        pop_front();
    }
}
 
template <typename T>
void List <T>::push_front(T data)
{
    if (Size > 1)
    {
        Node <T>* temp = head;
        head = new Node <T>(data, head);
        temp->pPrev = head;
    }
    else if (Size == 1)
    {
        head = new Node <T>(data, head);
        tail->pPrev = this->head;
    }
    else
    {
        head = tail = new Node <T>(data, head, tail);
    }
    Size++;
}
 
template <typename T>
void List <T>::push_back(T data)
{
    if (Size > 1)
    {
        Node <T>* temp = tail;
        tail = new Node <T>(data, nullptr, tail);
        temp->pNext = tail;
    }
    else if (Size == 1)
    {
        tail = new Node <T>(data, nullptr, tail);
        head->pNext = this->tail;
    }
    else
    {
        head = tail = new Node <T>(data, head, tail);
    }
    Size++;
}
 
template <typename T>
void List <T>::pop_front()
{
    if (Size > 1)
    {
        Node <T>* temp = head;
        head = head->pNext;
        delete temp;
    }
    else if (Size == 1)
    {
        Node <T>* temp = head;
        tail = head = head->pNext;
        delete temp;
    }
 
    Size--;
}
 
template <typename T>
void List <T>::pop_back()
{
    if (Size > 1)
    {
        Node <T>* temp = tail;
        tail = tail->pPrev;
        delete temp;
    }
    else if (Size == 1)
    {
        Node <T>* temp = tail;
        tail = head = tail->pPrev;
        delete temp;
    }
 
    Size--;
}
 
template <typename T>
void List <T>::insert(T data, int index)
{
    if (index == 0) push_front(data);
 
    else if (index == Size || index > Size) push_back(data);
 
 
    else if (index <= Size / 2)
    {
        Node<T>* previous = this->head;
        for (int i = 0; i < index - 1; i++)
        {
            previous = previous->pNext;
        }
 
        Node<T>* newNode = new Node<T>(data, previous->pNext, previous);
 
        previous->pNext = newNode;
        Node<T>* next = newNode->pNext;
        next->pPrev = newNode;
 
        Size++;
    }
 
    else if (index > Size / 2)
    {
        Node<T>* next = this->tail;
        for (int i = Size - 1; index < i; i--)
        {
            next = next->pPrev;
        }
 
        Node<T>* newNode = new Node<T>(data, next, next->pPrev);
 
        next->pPrev = newNode;
        Node<T>* previous = newNode->pPrev;
        previous->pNext = newNode;
 
        Size++;
    }
}
 
template <typename T>
void List <T>::removeAt(int index)
{
    if (index == 0) pop_front();
 
    else if (index == Size || index > Size) pop_back();
 
 
    else if (index <= Size / 2)
    {
        Node<T>* previous = this->head;
        for (int i = 0; i < index - 1; i++)
        {
            previous = previous->pNext;
        }
 
        Node<T>* toDelete = previous->pNext;
        previous->pNext = toDelete->pNext;
        Node<T>* next = toDelete->pNext;
        delete toDelete;
        next->pPrev = previous;
 
        Size--;
    }
 
    else if (index > Size / 2)
    {
        Node<T>* next = this->tail;
        for (int i = Size - 1; index < i; i--)
        {
            next = next->pPrev;
        }
 
        Node<T>* toDelete = next->pPrev;
        next->pPrev = toDelete->pPrev;
        Node<T>* previous = toDelete->pPrev;
        delete toDelete;
        previous->pNext = next;
 
        Size--;
    }
}
 
template <typename T>
T& List <T>::operator[] (const int index)
{
    if (index <= Size / 2)
    {
        int counter = 0;
        Node <T>* current = this->head;
 
        while (current != nullptr)
        {
            if (counter == index) return current->data;
            current = current->pNext;
            counter++;
        }
    }
    else
    {
        int counter = Size - 1;
        Node <T>* current = this->tail;
 
        while (current != nullptr)
        {
            if (counter == index) return current->data;
            current = current->pPrev;
            counter--;
        }
    }
}
 
template <typename T>
void List <T>::ShowData()
{
    std::cout << "Список:" << std::endl;
    std::cout << '\n';
    for (size_t i = 0; i < lst.GetSize(); i++) {
 
        std::cout <<lst[i]<< '|';
 
    }
    std::cout << '\n';
    std::cout << '\n';
}
template <typename T>
 
void List <T>::sort()
{
    Node <T>* left = head;                
    Node <T>* right = head->pNext;          
 
    Node <T>* temp = new Node<T>;              
    while (left->pNext) {                 
        while (right) {
            for (size_t i = 0; i < lst.GetSize(); i++) {
                if ((left->lst[i]) < (right->lst[i])) {   
                    temp->lst[i] = left->lst[i];          
                    left->lst[i] = right->lst[i];           
                    right->lst[i] = temp->lst[i];         
                }
                right = right->pNext;                  
            }
        }
        left = left->pNext;                             
        right = left->pNext;                            
    }
}
 
int main()
{
    SetConsoleOutputCP(1251);
    SetConsoleCP(1251);
 
 
    int n;
 
    for (int i = 0; i < 10; i++)
    {
        n = rand() % 99;
 
        lst.push_back(n);
 
    }
    while (true) {
 
        int variant;
        std::cout << "Выберите вариант \n" << std::endl;
        std::cout << "1. Добавить элемент \n"
            << "2. Изменить элемент \n"
            << "3. Удалить элемент \n"
            << std::endl;
        std::cout << ">>> ";
        std::cin >> variant;
 
 
 
        switch (variant) {
        case 1:
        {
            int N;
            int M;
            std::cout << "Добавить число: ";
            std::cin >> M;
            std::cout << "\n";
            std::cout << "Куда вставить: ";
            std::cin >> N;
            lst.insert(M, N);
            break;
        }
        case 2:
        {
            int N;
            int M;
            std::cout << "Какое число изменить: ";
            std::cin >> N;
            std::cout << "\n";
            std::cout << "На какое число изменить: ";
            std::cin >> M;
            lst.removeAt(N);
            lst.insert(M, N);
            break;
        }
        case 3:
        {
            int N;
            std::cout << "\n";
            std::cout << "Удалить число: ";
            std::cin >> N;
            lst.removeAt(N);            
            break;
        }
        case 4:
        {
            int N;
            lst.sort();
            lst.ShowData();
            break;
        }
        case 5:
        {
            lst.ShowData();
            break;
        }
        }
    }
 
    
    return 0;
}

template <typename T>
void List <T>::sort()
{
 
        Node<T>* previous = this->head;
        Node<T>* next = this->tail;
        Node<T>* sred = this->tail;
        for (int i = 0; lst.GetSize(); i++)
        {
            if (next > previous) {
                sred = next->pPrev;
                previous = previous->pNext;
                next =sred;
            }
        }
 
}

template <typename T>
void List <T>::sort()
{
    Node<T> *head2 = this->head;
    this->head = this->tail = nullptr;
    this->Size = 0;
    while (head2)
    {
        Node<T> *node = head2;
        head2 = head2.next;
 
        Node<T> *pos = this->upper_bound(node->data);
        this->insert_after(pos, node);
    }
}

template <typename T>
void List <T>::insert(T data, int index)
{
    if (index == 0) push_front(data);
 
    else if (index == Size || index > Size) push_back(data);
 
 
    else if (index <= Size / 2)
    {
        Node<T>* previous = this->head;
        for (int i = 0; i < index - 1; i++)
        {
            previous = previous->pNext;
        }
 
        Node<T>* newNode = new Node<T>(data, previous->pNext, previous);
 
        previous->pNext = newNode;
        Node<T>* next = newNode->pNext;
        next->pPrev = newNode;
 
        Size++;
    }
 
    else if (index > Size / 2)
    {
        Node<T>* next = this->tail;
        for (int i = Size - 1; index < i; i--)
        {
            next = next->pPrev;
        }
 
        Node<T>* newNode = new Node<T>(data, next, next->pPrev);
 
        next->pPrev = newNode;
        Node<T>* previous = newNode->pPrev;
        previous->pNext = newNode;
 
        Size++;
    }
}

template <typename T>
void List<T>::insert_after(T data, int index)
{
 
    if (index == 0)
    {
        push_front(data);
    }
    else
    {
        Node<T>* previous = this->head;
 
        for (int i = 0; i < index - 1; i++)
        {
            previous = previous->pNext;
        }
 
        Node<T>* newNode = new Node<T>(data, previous->pNext);
 
        previous->pNext = newNode;
 
        Size++;
    }
}

template <typename T>
void List <T>::insert_after(T data)
{
        Node<T>* previous = this->head;
        Node<T>* next = this->tail;
            previous = previous->pNext;
            next = next->pPrev;
}
 
 
template <typename T>
void List <T>::upper_bound(T data)
 
{
    if (head->data <= prev)
        return nullptr;
 
    auto p = head;
    while (p->next && p->next->data < prev)
        p = p->next;
 
    return p;
}
 
 
template <typename T>
void List <T>::sort()
{
    Node<T>* head2 = this->head;
    this->head = this->tail = nullptr;
    this->Size = 0;
    while (head2)
    {
        Node<T>* node = head2;
        head2 = head2.next;
 
        Node<T>* pos = this->upper_bound(node->data);
        this->insert_after(pos, node);
    }
}