2020q1 第一週測驗題

contributed by <timmycc>

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    LL0;

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                LL1;
            } else {
                LL2;
                merge = merge->next;
            }
            LL3;
        } else {
            if (!merge) {
                LL4;
            } else {
                LL5;
                merge = merge->next;
            }
            LL6;
        }
    }
    return start;
}

First, by the following code

    left = sort(left);
    right = sort(right);

we know the strategy taken by this algorithm is divide and conquer, and according to the name "merge", this should be a merge sort. So its behavior is like DIVIDE until there is one element only, then CONQUER easily.

The choice of LL0 is

(a) left->next = NULL
(b) right->next = NULL
(c) left = left->next
(d) left = right->next

(a) is the choice that match our strategy.

Next, the code assign sort(left) and sort(right) to left and right respectively, by the impression of divide and conquer, it's often return immediately when we input a simple case, and divide for other complex situation.

We have choose our divide at LL0, take a look at first for-loop, a pointer merge is point to a list, if left or right is a null pointer, then leave the loop.

Let's try to do divide on an example

after firt sort, the queue would become 1., and sort(right) would call sort once again, in the for-loop at second sort, left is point to 4 and right is point to 7, both of then are not point to null, but the usage of merge is still unknown, so refer the choice of LL1, LL2 and LL3

LL1 = ?
(a) start = left
(b) start = right
(c) merge = left
(d) merge = right
(e) start = merge = left
(f) start = merge = right

LL2 = ?
(a) merge->next = left
(b) merge->next = right

LL3 = ?
(a) left = left->next
(b) right = right->next
(c) left = right->next
(d) right = left->next

We inference the action that should be done when left < right, it's a sort, so we need a pointer point to the last object so that we can connect the following object, merge is the most possible things, if merge is null, then do LL1, it's need to assign the smaller one to merge, and also start, so (e) is the answer.

Else, means merge is point to something already, we have to assign left to merge->next, LL2 is (a).

After these, assign left->next to left, LL3 is (a).

By the same concept, the remaining is (f) (b) (b), and the full process of the previous example should be(simple version)

Finally, the function would be

list *sort(list *start) {
    if (!start || !start->next)
        return start;
    list *left = start;
    list *right = left->next;
    left->next = NULL;

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right; ) {
        if (!right || (left && left->data < right->data)) {
            if (!merge) {
                start = merge = left;
            } else {
                merge->next = left;
                merge = merge->next;
            }
            left = left->next;
        } else {
            if (!merge) {
                start = merge = right;
            } else {
                merge->next = right;
                merge = merge->next;
            }
            right = right->next;
        }
    }
    return start;
}