List.h
#include <stdio.h>
#include <stdlib.h>

typedef struct Node Node;
typedef int Data_T;
struct Node
{
	Data_T val_;
	Node* next_;
};



Node* Create_new (Node* el, Data_T val);

Node* Insert_end (Node* head, Data_T val);
Node* Insert (Node* head, int num, Data_T val);

Node* Del (Node* head, Data_T key);
void Print_List (Node* head);
int List_size (Node* head);
List.c

#include "list.h"


Node* Create_new (Node* el, Data_T val)
{
	el = malloc (sizeof (Node));
	el->val_ = val;
	el->next_ = NULL;
return el;
}

Node* Insert_end (Node* head, Data_T val)
{
	Node* t = head;
	if (head == NULL)
	   {
             head = Create_new (head, val);
             return head;
       }
	while (t->next_ != NULL) t = t->next_;

	Node* nw =	Create_new (nw, val);

	t->next_ = nw;
return head;
}

Node* Insert (Node* head, int num, Data_T val)
{
	Node* t = head;
	Node* nw = Create_new (nw, val);
	if (head == NULL)
        {
            if (num == 1)
                {
                    head = Create_new (head, val);
                    return head;
                }
            else
                {
                    printf("Out of range.\n");
                    return head;
                }
       }
	if (num == 1)
		{
			nw->next_ = head;
			return nw;
		}
	else
		{
			int i = 1;
			for (; i < num - 1 && t != NULL; i++)
				t = t->next_;

			if (i < num - 1)
				{
					printf ("Out of range\n");
					return head;
				}
			nw->next_ = t->next_;
			t->next_ = nw;
		}
return head;
}

void Print_List (Node* head)
{
	Node* t = head;
	if (head == NULL)
		{
			printf ("Empty\n");
			return;
		}
	while (t->next_ != NULL)
		{
			printf ("%d ", t->val_);
			t = t->next_;
		}
	printf ("%d\n", t->val_);
}

int List_size (Node* head)
{
	Node* t = head;
	if (head == NULL)
		{
			return 0;
		}
	int length = 0;
	while (t->next_ != NULL)
		{
			t = t->next_;
			length ++;
		}
return ++length;
}

Node* Del (Node* head, Data_T key)
{
	Node* t = head;
	if (t->val_ != key)
		{
			if (t->next_ == NULL)
				{
					printf ("No such value\n");
					return head;
				}
			while (t->next_->val_ != key && t->next_->next_ != NULL) t = t->next_;

			if (t->next_->val_ != key)
				{
					printf ("No such value\n");
					return head;
				}

			Node* t1 = t->next_->next_;
			free (t->next_);
			t->next_ = t1;
			return head;
	    }
    if (head->next_ != NULL)
        {
            Node* new_head = head->next_;
            free (head);
            return new_head;
        }
    else return NULL;
}
main.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "list.h"
int Max = 256;

Node* merge (Node* el1, Node* el2);
Node* merge_sort (Node* head);

Node* merge(Node* el1, Node* el2)
{
    Node* t1 = el1;
    Node* t2 = el2;
    Node* res = malloc (sizeof (Node));
    Node* el = res;
    while (1){
      if (t1 == NULL && t2 == NULL)
      break;
      if ((t1 == NULL) && (t2 != NULL)){
            el->val_ = t2->val_;
            t2 = t2->next_;
            if (t2 != NULL){
                el->next_ = malloc(sizeof(Node));
                el = el->next_;
            }
      }
      else if ((t2 == NULL) && (t1 != NULL)){
            el->val_ = t1->val_;
            t1 = t1->next_;
            if (t1 != NULL){
                el->next_ = malloc(sizeof(Node));
                el = el->next_;
            }
      }
      else if (t1->val_ <= t2->val_){
         el->val_ = t1->val_;
         el->next_ = malloc(sizeof(Node));
         el = el->next_;
         t1 = t1->next_;
      }
      else{
         el->val_ = t2->val_;
         el->next_ = malloc(sizeof(Node));
         el = el->next_;
         t2 = t2->next_;
      }


   }
   el->next_ = NULL;
   return res;
}

Node* merge_sort (Node* head)
{
    if (List_size(head)>2){
        int middle = (List_size(head)-1)/2;
        Node* h = head;
        Node* temp1 = malloc (sizeof (Node));
        Node* temp2 = temp1;
        Node* temp3 = malloc (sizeof (Node));
        Node* temp4 = temp3;
        Node* temp5 = malloc (sizeof (Node));
        Node* temp6 = malloc (sizeof (Node));
        temp1->val_ = h->val_;
        temp1->next_ = (Node*) malloc(sizeof(Node));
        temp1 = temp1->next_;
        h = h->next_;
        for (int i=0; i<middle-1; i++){
            temp1->val_ = h->val_;
            h = h->next_;
            temp1->next_ = (Node*) malloc(sizeof(Node));
            temp1 = temp1->next_;
        }
        temp1->val_ = h->val_;
        h = h->next_;
        temp1->next_ = NULL;
        temp3->val_ = h->val_;
        h = h->next_;
        if (h != NULL){
            temp3->next_ = (Node*) malloc(sizeof(Node));
            temp3 = temp3->next_;
            for (int i=middle+1; i<List_size(head)-2; i++){
                temp3->val_ = h->val_;
                temp3->next_ = (Node*) malloc(sizeof(Node));
                temp3 = temp3->next_;
                h = h->next_;
            }
            temp3->val_ = h->val_;
        }
        temp3->next_ = NULL;
        temp5 = merge_sort(temp2);
        temp6 = merge_sort(temp4);
        return merge(temp5, temp6);
    }
    else {
        if (head->next_ != NULL){
            Node* temp1 = head;
            Node* temp2 = head->next_;
            temp1->next_ = NULL;
            return merge(temp1, temp2);
        }
        else return head;
    }
}

int main ()
{
    Node* head = NULL;
    char str [Max];
    int t = 0;
    int t1 = 0;
    int n = 0;
    printf("Commands:\n");
	printf("i (index) <value> - insert value into the list\n");
	printf("p - print the list\n");
	printf("l - print the list size\n");
	printf("d <value> - delete the first occurance of value in the list\n");
    printf("s - sort the list\n");
    while (fgets (str, Max, stdin) != NULL)
        {
            switch (str [0])
            {
            case 'i' :  n = sscanf (str, "i %d %d", &t, &t1);
                        if (n == 2) head = Insert (head, t, t1);
                        else if (n == 1) head = Insert_end (head, t);
                        else printf("Wrong input.");
                        break;
            case 'p' :  Print_List (head);
                        break;
            case 'l' :  printf ("Size is %d\n", List_size (head));
                        break;
            case 'd' :  n = sscanf (str, "d %d", &t);
                        if (head == NULL)
                            {
                                printf("List is empty.\n");
                                break;
                            }
                        if (n == 1) head = Del (head, t);
                        else printf("Wrong input.");
                        break;
             case 's':  if (List_size(head) <= 1);
                        else head = merge_sort(head);
                        break;

            default  :  printf("Could not recognize the command.\n");
                        break;
            }
        str [0] = 0;
        }
return 0;
}