#include <iostream>
#include <string>
using std::string;
using std::cout;
// сортировка слиянием
template<typename T>
T* merge_sort(T* lst, T** ptail, bool (*pred_cmp)(const T*, const T*)) {
if((lst == NULL) || (lst->next == NULL))
return lst;
T* ptr, *next, *tail;
T* iter = lst;
T* last = lst;
ptr = next = tail = NULL;
for(T* tmp = lst; (tmp != NULL) && (tmp->next != NULL); tmp = tmp->next->next) {
last = iter;
iter = iter->next;
}
last->next = NULL;
lst = merge_sort(lst, ptail, pred_cmp);
iter = merge_sort(iter, ptail, pred_cmp);
for(; (lst != NULL) || (iter != NULL); ) {
if(iter == NULL) {
next = lst;
lst = lst->next;
} else if(lst == NULL) {
next = iter;
iter = iter->next;
} else if((*pred_cmp)(lst, iter)){
next = lst;
lst = lst->next;
} else {
next = iter;
iter = iter->next;
}
if(ptr == NULL)
ptr = next;
else
tail->next = next;
next->prev = tail;
tail = next;
}
*ptail = tail;
return ptr;
}
// здесь кусок кода для наглядности сортировки
typedef unsigned short int USI;
struct School {
USI number,primary,middle,senior;
string district;
School *next;
School *prev;
} info;
// добавление в хвост
void AddBack(School** head, School** tail, USI number, USI primary,
USI middle, USI senior, const string& district) {
School* snew = new School();
snew->number = number;
snew->primary = primary;
snew->middle = middle;
snew->senior = senior;
snew->district = district;
if(*head != NULL) {
snew->next = snew;
snew->prev = *tail;
snew->prev->next = snew;
*tail = snew;
} else {
*head = snew;
snew->next = *head;
snew->prev = NULL;
*tail = *head;
}
(*tail)->next = NULL;
}
// удаление из головы
void PopHead(School** head, School** tail) {
if(*head == NULL)
return;
if(*head == *tail) {
delete *head;
*head = *tail = NULL;
return;
}
School* tmp = *head;
*head = (*head)->next;
(*head)->prev = NULL;
delete tmp;
}
//
bool func_cmp(const School* a, const School* b) {
return (a->primary+a->middle+a->senior) > (b->primary+b->middle+b->senior);
}
int main(void) {
School* head = NULL;
School* tail = NULL;
//...
for(int i = 1; i <= 255; i++) {
AddBack(&head, &tail, (USI)i, (USI)(rand()%255),
(USI)(rand()%255), (USI)(rand()%255), "Sample");
}
// отсортируем список
head = merge_sort(head, &tail, &func_cmp);
//...
for(;head != NULL; PopHead(&head, &tail))
cout << "sum: " << (head->primary+head->middle+head->senior) << std::endl;
return 0;
}