연결 리스트 정렬

합병 정렬

void split_list(GraphNode *node, GraphNode **front_ref, GraphNode **back_ref){
    GraphNode *fast;
    GraphNode *slow;
    slow = node;
    fast = node->link;

    while(fast != NULL){
        fast = fast->link;
        if(fast != NULL){
            slow = slow->link;
            fast = fast->link;
        }
    }

    *front_ref = node;
    *back_ref = slow->link;
    slow->link = NULL;
}

GraphNode* sorted_merge(GraphNode *a, GraphNode *b){
    GraphNode *result = NULL;

    if(a == NULL)
        return b;
    else if(b == NULL)
        return a;
    
    if(a->vertex >= b->vertex){
        result = a;
        result->link = sorted_merge(a->link, b);
    } else{
        result = b;
        result->link = sorted_merge(a, b->link);
    }
    return result;
}

GraphNode* merge_sort(GraphNode *node){
    if(node == NULL || node->link == NULL){
        return node;
    }

    GraphNode *a;
    GraphNode *b;

    split_list(node, &a, &b);

    a = merge_sort(a);
    b = merge_sort(b);

    return sorted_merge(a, b);
}

합병 정렬의 경우 시간복잡도는 O(n log n)으로 큰 문제를 작은 문제로 분할하여 해결하기 때문에 일반적인 정렬에 비해 시간 복잡도가 낮으며 특히 많은 데이터를 정렬할 때 사용하면 효율적이다.

내림차순의 합병 정렬 과정은 다음과 같다.