#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next, *prev;
};
void display(struct node *start) {
struct node *temp = start;
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != start);
printf("\n");
}
void append(struct node **start, int value) {
if (!*start) {
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = new_node->prev = new_node;
*start = new_node;
return;
}
struct node *last = (*start)->prev;
struct node *new_node = malloc(sizeof(struct node));
new_node->data = value;
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
last->next = new_node;
}
struct node *find_mid(struct node **start) {
int count = 0;
if (!*start)
return NULL;
struct node *temp = *start;
do {
count++;
temp = temp->next;
} while (temp != *start);
int mid_index = (count + 1) / 2;
temp = *start;
for (int i = 1; i < mid_index; i++)
temp = temp->next;
return temp;
}
void merge(struct node **start1, struct node **start2) {
struct node *temp1 = *start1;
struct node *temp2 = *start2;
struct node *last = NULL;
(*start1)->prev->next = NULL;
(*start2)->prev->next = NULL;
if (temp1->data < temp2->data) {
last = *start1;
temp1 = temp1->next;
} else {
*start1 = *start2;
last = *start2;
temp2 = temp2->next;
}
while (temp1 != NULL && temp2 != NULL) {
if (temp1->data < temp2->data) {
last->next = temp1;
temp1->prev = last;
last = temp1;
temp1 = temp1->next;
} else {
last->next = temp2;
temp2->prev = last;
last = temp2;
temp2 = temp2->next;
}
}
if (temp1) {
last->next = temp1;
temp1->prev = last;
}
if (temp2) {
last->next = temp2;
temp2->prev = last;
}
while (last->next != NULL)
last = last->next;
(*start1)->prev = last;
last->next = *start1;
}
void merge_sort(struct node **start) {
struct node *last = (*start)->prev;
if (last == *start)
return;
struct node *mid = find_mid(start);
struct node *start2 = mid->next;
mid->next = *start;
(*start)->prev = mid;
last->next = start2;
start2->prev = last;
merge_sort(start);
merge_sort(&start2);
merge(start, &start2);
}
int main()
{
struct node *start1 = NULL;
struct node *start2 = NULL;
struct node *start = NULL;
append(&start, 5);
append(&start, 6);
append(&start, 6);
append(&start, 13);
append(&start, 6);
append(&start, 87);
append(&start, 6);
append(&start, 10);
append(&start, 7);
merge_sort(&start);
display(start);
return 0;
}