Decision tree with recursive sort algorithm

I was wondering if someone can help me understand how to create a decision tree for a recursive sort. I understand how to do it with, say, bubble sort or insertion sort. When it comes to a recursive sort, though, I just can't picture it. If the pseudo-code is something like:

if length == 1
    return;
else
    int elem = head of array;
    array tail = tail of array;
    recursive sort;
    if (elem <= head of sorted list)
        add elem to the beginning of sorted list
    else
        swap elem and first element of sorted list
        sort smaller list again
        add elem to the beginning of sorted list
return

My initial thought is that the decision tree would look like the following:

                               A, B, C
                           yes /     \ no  is length <= 1?
                              /       \
                                      remove head
                                        /   \
                                       A    B, C
                                        yes /   \ no  is length <= 1?
                                           /     \
                                                remove head
                                                  /   \
                                                  B   C
                                                 yes /   \ no   is length <= 1?
                                                    /     \
                                                 B:C
                                                /   \
                                              B,C   C,B
                                             |         |
                                          A:B,C       A:C,B
                                         /   \        /   \
                                     A,B,C   B:A,C  A,C,B  C:A,B
                                             /  开发者_如何学Python\          /   \
                                        B,A,C   A:B,C   C,A,B  A:C,B

I am obviously going wrong somewhere, I'm just not quite sure where. Am I on the right track here?

Thank you for any pointers you can give me.

(Is this homework?)

Look at your code again! You're currently branching both ways inside the if-then-else construct. Fix that and you should get a single correct result.

Also, you're unwinding the call stack down there, so going back up would be "more correct". Wikipedia might give you an idea of how this works.

Good luck!

Following your representation, the result would be something like this:

                            A, B, C
                       yes /     \ no  is length <= 1?
                          /       \
                                  remove head
                                    /   \
                                   A    B, C
                                    yes /   \ no  is length <= 1?
                                       /     \
                                            remove head
                                              /   \
                                              B   C
                                             yes /   \ no   is length <= 1?
                                                /     \
                                             B:C
                                            /   \
                                          B,C   C,B
                                         |         |
                                      A:B,C       A:C,B
                                     /   \        /   \
                                 A,B,C   B:A,C  A,C,B  C:A,B
                                         /  \          /   \
                                    B,A,C   **B,C,A**   C,A,B  **C,B,A**

In the last step, you decide if swapping is needed or the two at the left side are sorted. If they are, there's no need to keep sorting since the right side is sorted, if they're not, you first swap the leftmost elements, and sort the two at the right.

e.g., B:A,C --swap-> A:B,C --sort-> A,B,C or A,C,B.

I hope it helps you.