Восходящая сортировка связных списков слиянием.

[VAAKAraceGUM]

Здравствуйте, мне дали задание сделать восходящую сортировку связного списка слиянием .
Собственно моя программа (создание двусвязного списка, добавление элемента в любое место, удаление из любого места, печать ) выглядит так :

PHP код:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct stack
{
    int val;
    struct stack * next;
    struct stack * prev;
};
struct stack * root;
struct stack * last;
int add_val (int where, int pos, int kol);
int del_val (int pos, int kol);
void print_stack (unsigned int num);
int main ()
{
    root = (struct stack *) malloc (sizeof (struct stack));
    last = root;
    int count = 0;
    int pos;
    int choise_where;
    char choise;
    
    while (choise != 'q')
    {
        printf ("\nКоманды:\n");
        printf ("\"a\" - добавление элемента в список;\n");
        printf ("\"d\" - удаление элемента из списка;\n");
        printf ("\"q\" - выход;\n");
        printf ("Ваш выбор: ");
        scanf (" %c", &choise);
        
        if (choise == 'a')
        {
            printf ("\nУкажите, как добавить: \n");
            printf ("1) создать новый элемент\n");
            printf ("2) после элемента\n");
            printf ("3) перед элементом\n");
            printf ("4) вместо элемента\n");
            printf ("Ваш выбор: ");
            scanf (" %d", &choise_where);
            
            if (choise_where < 1 || choise_where > 4)
            {
                printf ("Нет такого варианта!\n");
                continue;
            }
            if (choise_where != 1)
            {
                printf ("Позиция (номер элемента): ");
                scanf (" %d", &pos);
            }
            count = add_val (choise_where, pos, count);
            print_stack (count);
        }
        else if (choise == 'd')
        {
            printf ("Позиция, откуда удалить: ");
            scanf (" %d", &pos);
            count = del_val (pos, count);
            print_stack (count);
        }
        else if (choise == 'q') return 0;
        else printf ("Нет такого варианта!\n");
    }
    return 0;
}
int add_val (int where, int pos, int kol)
{
    int value, iter;
    struct stack *ptr_one, *ptr_two;
    struct stack *nov = (struct stack*) malloc (sizeof (struct stack));
    
    printf ("Значение (целое число): ");
    scanf (" %d", &value);
    ptr_one = root;
    if (where == 1)
    {
        last->val = value;
        last->next = nov;
        nov->prev = last;
        last = last->next;
        return ++kol;
    }
    
    if (pos > kol || pos < 1)
    {
        printf ("Ошибка, нет %d-ого элемента!\n", pos);
        return kol;
    }
    for (iter = 1; iter < pos; iter++)
        ptr_one = ptr_one->next;
    if (where == 2)
    {
        nov->val = value;
        ptr_two = ptr_one->next;
        ptr_one->next = nov;
        nov->prev = ptr_one;
        nov->next = ptr_two;
        ptr_two->prev = nov;
        return ++kol;
    }
    if (where == 3)
    {
        nov->val = value;
        if (pos == 1) root->prev = (struct stack*) malloc (sizeof (struct stack));
        ptr_two = ptr_one->prev;
        ptr_one->prev = nov;
        nov->next = ptr_one;
        nov->prev = ptr_two;
        ptr_two->next = nov;
        if (pos == 1) root = nov;
        return ++kol;
    }
    if (where == 4)
        ptr_one->val = value;
        
    return kol;
}
int del_val (int pos, int kol)
{
    int iter;
    struct stack *ptr;
    ptr = root;
    if (pos > kol || pos < 1)
    {
        printf ("Ошибка, нет %d-ого элемента!\n", pos);
        return kol;
    }
    for (iter = 1; iter < pos; iter++)
        ptr = ptr->next;
    if (pos == 1)
    {
        root = root->next;
        free (root->prev);
    }
    else if (pos == kol)
    {
        last = last->prev;
        free (last->next);
    }    
    else
    {
        (ptr->prev)->next = ptr->next;
        (ptr->next)->prev = ptr->prev;
        free (ptr);
    }
    return --kol;
}
void print_stack (unsigned int num)
{
    int go;
    if (num == 0)
    {
        printf ("\nСПИСОК ПУСТ!\n");
        return;
    }
    printf ("\nСПИСОК: ");
    struct stack* out = root;
    for (go = 0; go < num; go++)
        {
        printf ("%d ", out->val);
        out = out->next;
        }
    printf ("\n");
} 


Соответственно, мне надо сделать эту злополучную Восходящую сортировку связного списка слиянием.Помогите плз, а то я чет не до конца понимаю как тут эту сортировку организовать...