Реализация связи элементов линейного списка - указатели. Способ организации линейного связанного списка - дек.
Алгоритм сортировки - Естественное двухпутевое слияние. Не могу написать код сортировки, сам алгоритм понял, а с кодом разобраться не могу. Помогите заочнику закрыть задолжность

Вот программа без сортировки

#include "stdafx.h"
#include "iostream"

using namespace std;

struct Value
{
public:int val;
Value* Next;
Value* Prev;
Value(int n):Next(0),Prev(0),val(n){};
};
class deq
{
Value* Head;
Value* Tail;
public:void Add_First(int n);
public:void Add_Last(int n);
public:void Delete_First();
public:void Delete_Last();
public:void Print();
public:void Sort();
public:deq(){Head=NULL;Tail=NULL;}
};
void deq::Add_First(int n)
{
Value* Elem=new Value(n);
Elem->Prev=NULL;
if (Head!=NULL)
{
Elem->Next=Head;
Head->Prev=Elem;
Head=Elem;
}
else
{
Elem->Next=NULL;
Head=Tail=Elem;
}
}
void deq::Add_Last(int n)
{
Value* Elem=new Value(n);
Elem->Next=NULL;
if (Tail!=NULL)
{
Elem->Prev=Tail;
Tail->Next=Elem;
Tail=Elem;
}
else
{
Elem->Next=NULL;
Tail=Head=Elem;
}
}
void deq::Delete_First()
{
Value *p;
p=Head->Next;
delete Head;
Head=p;
p->Prev=NULL;
}
void deq::Delete_Last()
{
Value *p;
p=Tail->Prev;
delete Tail;
Tail=p;
p->Next=NULL;
}
void deq::Print()
{
Value *p=Head;
while(p!=NULL)
{
cout<<p->val<<" ";
p=p->Next;
}
cout<<"\n";
}
void deq::Sort()
{}
int main()
{ deq elements;

elements.Add_First(15);
elements.Add_First(1);
elements.Add_First(3);
elements.Add_First(7);
elements.Add_First(9);
elements.Add_Last(4);
elements.Add_Last(6);
elements.Print();
elements.Sort();
cout << "\n";
elements.Print();

system("pause");
return 0;
}