Сортировка списка

class List {
private:
    struct ListItem {
        int item;
        ListItem *next;
 
        ListItem (int i, ListItem *n = NULL){
            item = i;
            next = n;       
        }
    };
 
    int itemsCount;
    ListItem *first;
    ListItem *last;
 
public:
    List(){
        itemsCount = 0;
        first = last = NULL;
    }
 
    ~List();
        int Head() {
        return first->item;
    }
        int Tail() {
        return last->item;
    }
 
    void AddFirst (int item);
    void AddLast (int item);
    void DeleteFirst();
    void DeleteLast();
 
    void ShowList();
};

void List::sort(){
Listitem* unsortedlist=first->next;
ListItem* ins_item, counter, pre;
first->next=NULL;//начинаем создавать новый список, перемещая в него элементы из несортированной части по очереди
while(unsortedlist){
  ins_item=unsortedlist;//элемент для вставки - первый в неотсортированной части
  unsortedlist=unsortedlist->next;// удаляем его из неё
  counter=first; //counter \указатель на место, куда вставить в отсортированную часть
  pre=NULL;
  while(counter){//ищем это место пока отсорт. часть не закончится...
   if (ins_item->item>counter->item){
     pre=counter;                             //при этом перемещаем указатель по отсортированной части
     counter=counter->next;              // запоминая, текущее и предыдущее место
     }
     else{
      break;//...или не найдём место, куда вставить элемент.
     }
  }
  if(pre) pre->next=ins_item;// вставляем элемент между предыдущим
  ins_item->next=counter;//и текущим элементом в отсортированной части
}
 
}

#include <stddef.h>
 
static void insertion_sort(int *a, const size_t n) {
    size_t i, j;
    int value;
    for (i = 1; i < n; i++) {
        value = a[i];
        for (j = i; j > 0 && value < a[j - 1]; j--) {
            a[j] = a[j - 1];
        }
        a[j] = value;
    }
}
 
int main(void) {
    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
    insertion_sort(a, sizeof a / sizeof a[0]);
    return 0;
}

void List::Sort()
{
    ListItem *current = first;
    ListItem *temp;
    current = current->next; //просто чтоб с головой не заморачиваться, сравниваю 2 и 3 эл-т
 
    if (current->item > current->next->item){
        temp = current->next;
        current->next = current;
        current = temp;
    }   
}

current-----v       |--------v      |----
            |item|next|   |item|next|

                                      тут связь потеряна
current-----v      |------|                 |----
           |item|next|<---|       |item|next|

(pre-первый элемент, current второй, current->next третий, current->next->next четвёртый)
pre->next=current->next;//разрываем связь первого со вторым,
///////////////////////// связываем первый с третьим 
current->next=current->next->next;//разрываем связь 2го и 3го, 
////////////////////////////////////связываем второй с четвёртым
pre->next->next=current;//pre->next - бывший третий элемент
/////////////////////////разрываем его связь с четвёртым
/////////////////////////и связываем со вторым

...............pre......................current......
.................|.......................|
.................v......|----------v.....v.....|----v......|-------v......
.............|item1|next|....|item2|next|....|item3|next|....|item4|next|
 
pre->next=current->next;
...............pre.............current......
.................|...................|
.................v...................v........|-------v........|-------v......
.............|item1|next|....|item2|next|....|item3|next|....|item4|next|
..........................|----------------------^
 
current->next=current->next->next;
 
...............pre.............current......
.................|...................|.........----------------------------|
.................v...................v.......|......................|-------v.....v...
.............|item1|next|....|item2|next|....|item3|next|....|item4|next|
.........................|----------------------^
 
pre->next->next=current;
 
...............pre.............current......
.................|...................|........-------------------------|
.................v...................v......|.............................v...
............|item1|next|....|item2|next|....|item3|next|....|item4|next|
.......................|-------------------------^...|
.....................................^------------------|
 
и того 
item1->next=item3
item3->next=item2
item2->next=item4