sort

#include <cstdio>
#include <iostream>

using namespace std;
/*
void merge(int *a, int left, int mid, int right)
{
    int *LeftBuf = (int*)malloc(sizeof(int)*(mid - left+1));
    int *RightBuf = (int*)malloc(sizeof(int)*(right - mid));
    int i, j=0;
    int k = left;
    for (i = 0; i < mid - left+1; i++)
    {
        LeftBuf[i] = a[i + left]; //заполняется левый буферный массив из исходного
    }
    for (i = 0; i <= right - mid-1; i++)
    {
        RightBuf[i] = a[i + mid+1]; //заполняется левый буферный массив из исходного
    }
    i = 0;
    while ((i < mid - left+1) && (j < right - mid))
    {
        if (LeftBuf[i] <= RightBuf[j])
        {
            a[k] = LeftBuf[i];
            i++;
        }
        else{
            a[k] = RightBuf[j];
            j++;
        }
        k++;
    }
    while (i < mid-left+1)
    {
        a[k] = LeftBuf[i];
        k++;
        i++;
    }
    while (j < right-mid)
    {
        a[k] = RightBuf[j];
        k++;
        j++;
    }
}

void merge_sort(int*A, int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        merge_sort(A, left, mid);
        merge_sort(A, mid + 1, right);
        merge(A, left, mid, right);
        for (int i = 0; i < 5; i++)
            cout << A[i] << " ";
        printf("\n");
    }
}*/
struct list_element;
list_element *push_back(list_element *head, int key);
void show_list(list_element *head);
int get_key(list_element *head, int number);
void set_key(list_element *head, int number, int key);

void insertSort(int *a, int n)
{
    int i,j, m, key;
    for (j = 0; j < n; j++)
    {
        key = a[j];
        i = j-1;
        while (i >= 0 && a[i] > key)
        {
            a[i + 1] = a[i];
            i--;
        }
        a[i + 1] = key;
    }
}

void merge(list_element *head, int left, int mid, int right)
{
    list_element *head_left=NULL;
    list_element *head_right=NULL;
    list_element *tmp=head_left;
    int i, j = 0;
    int k = left;
    for (i = 0; i < mid - left + 1; i++)
    {
        head_left=push_back(head_left, get_key(head, i + left));
    }
    tmp = head_right;
    for (i = 0; i <= right - mid - 1; i++)
    {
        head_right=push_back(head_right, get_key(head, i + mid + 1));
    }

    i = 0;
    while ((i < mid - left + 1) && (j < right - mid))
    {
        if (get_key(head_left, i) <= get_key(head_right, j))
        {
            set_key(head, k, get_key(head_left, i));
            i++;
        }
        else{
            set_key(head, k, get_key(head_right, j));
            j++;
        }
        k++;
    }
    while (i < mid - left + 1)
    {
        set_key(head, k, get_key(head_left, i));
        k++;
        i++;
    }
    while (j < right - mid)
    {
        set_key(head, k, get_key(head_right, j));
        k++;
        j++;
    }
}

void merge_sort(list_element *head, int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        merge_sort(head, left, mid);
        merge_sort(head, mid + 1, right);
        merge(head, left, mid, right);
    }
}

struct list_element
{
    int key=0;
    list_element *next=0;
    list_element(){};
};

list_element *push_back(list_element *head, int key)
{

    list_element *new_elem = new list_element;
    new_elem->key = key;
    if (head == NULL)
    {
        head = new_elem;
        return head;
    }
    list_element *tmp = head;
    while (tmp->next != 0)
    {
        tmp = tmp->next;
    }
    tmp->next = new_elem;
    return head;
}

int get_key(list_element *head, int number)
{
    list_element *tmp=head;
    while (number > 0)
    {
        tmp = tmp->next;
        number--;
    }
    return tmp->key;
}
void set_key(list_element *head, int number,int key)
{
    list_element *tmp = head;
    while (number > 0)
    {
        tmp = tmp->next;
        number--;
    }
    tmp->key = key;
}

void show_list(list_element *head)
{
    list_element *tmp = head;
    while (tmp != 0)
    {
        cout << tmp->key << " ";
        tmp = tmp->next;
    }
    cout <<endl;
}

int main()
{
    int i;
    int a[8] = { 6, 1, 4, 0, 9, 0, 9, 4};
    int length = sizeof(a) / sizeof(*a);
    list_element *head = NULL;
    for (i = 0; i < length; i++)
    {
        head = push_back(head, a[i]);
    }
    show_list(head);
    merge_sort(head, 0, length-1);
    cout << "Merge sort: ";
    show_list(head);
    cout << "Insert sort: ";
    insertSort(a, length);
    for (i = 0; i < length; i++) cout << a[i] << " ";
    return 0;
}