+ first->next = second;
+ return head_first;
+}
+
+link_t* list_sort(link_t* head) {
+ int tmp;
+ bool isswaped;
+ link_t* head_first = head;
+
+ do {
+ isswaped = false;
+ while (head->next != NULL) {
+ if (head->value > head->next->value) {
+ tmp = head->value;
+ head->value = head->next->value;
+ head->next->value = tmp;
+ isswaped = true;
+ }
+ head = head->next;
+ }
+ /* Reloop at the beginning of the list until there's values swaped */
+ head = head_first;
+ } while (isswaped);
+ return head_first;
+}
+
+static link_t* _list_merge_sort(link_t* head1, link_t* head2) {
+ link_t* head_result = NULL;
+
+ if (head1 == NULL) {
+ return head2;
+ }
+ if (head2 == NULL) {
+ return head1;
+ }
+ if (head1->value < head2->value) {
+ head_result = head1;
+ head_result->next = _list_merge_sort(head1->next, head2);
+ } else {
+ head_result = head2;
+ head_result->next = _list_merge_sort(head1, head2->next);
+ }
+ return head_result;
+}
+
+link_t* list_merge_sort(link_t* head) {
+ link_t* head1;
+ link_t* head2;
+
+ if (head == NULL || head->next == NULL) {
+ return head;
+ }
+
+ head1 = head;
+ head2 = head->next;
+ while (head2 != NULL && head2->next != NULL) {
+ head = head->next;
+ head2 = head->next->next;
+ }
+ head2 = head->next;
+ head->next = NULL;
+
+ head1 = list_merge_sort(head1);
+ head2 = list_merge_sort(head2);
+ return _list_merge_sort(head1, head2);