#include <stdio.h>

void swap(int &a, int &b){ int tmp = a; a = b; b = tmp; }

struct ListNode {
    ListNode(int value_, ListNode *next_):
        value(value_), next(next_) {}

    int value;
    ListNode *next;
};

struct List { // singly linked list
    List(): begin(NULL) {}
    List(const List &list): begin(NULL) {
        ListNode tmp(0, NULL); // for convenience
        ListNode *end = &tmp;
        for(ListNode *p = list.begin; p != NULL; p = p->next){
            end->next = new ListNode(p->value, NULL);
            end = end->next;
        }
        begin = tmp.next;
        // P.S. If you directly use push, the order will be revered.
    }
    List(const List &list, ListNode *first, ListNode *last): begin(NULL) {
        ListNode tmp(0, NULL); // for convenience
        ListNode *end = &tmp;
        for(ListNode *p = first; p != last; p = p->next){
            end->next = new ListNode(p->value, NULL);
            end = end->next;
        }
        begin = tmp.next;
    }
    ~List(){
        for(ListNode *p = begin, *q; p != NULL; p = q){
            q = p->next;
            delete p;
        }
    }
    void push(int value){
        begin = new ListNode(value, begin);
    }
    void print() const {
        for(ListNode *p = begin; p != NULL; p = p->next)
            printf("%d ", p->value);
    }

    ListNode *begin;
};

void selection_sort(List &list){
    for(ListNode *p = list.begin; p != NULL; p = p->next)
        for(ListNode *q = p->next; q != NULL; q = q->next)
            if(q->value < p->value)
                swap(q->value, p->value);
}

void merge_selection_sort(List &list){
    // fast-slow pointer to find node at middle
    ListNode *m = list.begin;
    for(ListNode *p = list.begin; p != NULL; p = p->next, m = m->next)
        if((p = p->next) == NULL)
            break;
    // partition
    List l1(list, list.begin, m), l2(list, m, NULL);
    selection_sort(l1);
    selection_sort(l2);
    // merge
    ListNode *p1 = l1.begin, *p2 = l2.begin;
    ListNode *end = list.begin;
    while(p1 != NULL && p2 != NULL){
        if(p1->value < p2->value){
            end->value = p1->value;
            p1 = p1->next;
        }else{ // p1->value >= p2->value
            end->value = p2->value;
            p2 = p2->next;
        }
        end = end->next;
    }
    for(ListNode *p = p1 == NULL? p2 : p1; p != NULL; p = p->next){
        end->value = p->value;
        end = end->next;
    }
}

int main(){
    List list;

    list.push(-9);
    list.push(1);
    list.push(3);
    list.push(4);
    list.push(3);
    list.push(0);
    list.push(8);
    list.push(8);
    list.push(1);
    list.push(7);
    list.print(); putchar('\n');

    // selection_sort(list);
    merge_selection_sort(list);
    list.print(); putchar('\n');
    
    return 0;
}