Отсортировать введенные записи по возрастанию значений ключей - C (СИ)

Формулировка задачи:

С клавиатуры ввести набор записей с полями: <Ключ> <Сообщение> (ключ - целое число). Отсортировать введены записи по возрастанию значений ключей. В отсортированный массив ввести две новые записи так, чтобы сохранить общую упорядоченность массива. Распечатать результирующий массив. ( Использовать функции). Помогите пожалуйста уже почти неделю сижу.

Решение задачи: «Отсортировать введенные записи по возрастанию значений ключей»

Листинг программы

struct Node
{
    int val;
    Node *next;
    Node(int n) {       // Интуитивная инициализация
        val = n;
        next = NULL;
    }
};
 
struct List
{
    Node *first;
    List() {
        first = NULL;
    }
};
 
Node *obrat(List *list1, List **list2)
{
    Node *temp, *temp2;/*2 указателя*/
    List *list2 = NULL;/*list2 присвоен NULL*/
    temp = list1->first;/*temp указывает на list1*/
    while (temp)/*Пока не пуст*/
    {
        temp2 = temp->next;/*temp2 указывает на предыдущий temp-у элемент*/
        temp->next = *list2;/*Предыдущий temp-y элемент указывает на верхушку list2*/
        *list2 = temp;/*list2 указывает на верхушку temp*/
        temp = temp2;/*temp указывает на temp2, т.е. перешли на предыдущую ячейку*/
    }
    return temp;
}

Объяснение кода листинга программы

В данном коде реализован алгоритм двусвязного списка, который, скорее всего, используется для хранения и сортировки данных.

Структура Node представляет собой элемент списка и содержит в себе значение val и указатель next на следующий элемент списка.
Структура List представляет собой список и содержит в себе указатель first на первый элемент списка.
Функция obrat(List *list1, List **list2) принимает два указателя: на список, который нужно отсортировать (list1), и на указатель на вершину второго списка (list2). В данной реализации list2 инициализируется как NULL.
Внутри функции создаются два указателя: temp и temp2. temp указывает на первый элемент списка list1, а temp2 - на предыдущий элемент temp.
Затем происходит обход списка list1 до тех пор, пока temp не станет NULL.
В процессе обхода каждый элемент temp добавляется в начало списка list2 путем изменения указателя temp2 на temp и обновления указателя temp на temp2.
В конце функции возвращается temp, который будет указывать на последний добавленный в list2 элемент. Таким образом, данный код, скорее всего, реализует сортировку списка по возрастанию значений ключей.