Start New Discussion within our Software Development Community

Hi,
i understand merge sort & quick sort even i can write the programs but iam unable to understand its complexity.

its very easy to derive complexity equations for selection & bubble sort.

as the code is little complex & recursive nature i am unable to understand its complexity and how its n log n.


please some one provide me some easy method to understand its complexity.

considering 16 elements in the list.

selection & bubble it takes O(n2);

but quick and merge 16 * 4 = 64.

All you're doing with the divide and conquer is breaking up the list into smaller lists, then putting the sorted smaller lists back together. This breakdown and rebuilding is an O(logn) operation:

0 1 2 3 4 5 6 7 8 9 A B C D E F
0 1 2 3 4 5 6 7
0 1 2 3
0 1
    2 3
0 1 2 3
        4 5 6 7
        4 5
            6 7
        4 5 6 7
0 1 2 3 4 5 6 7
                8 9 A B C D E F
                8 9 A B
                8 9
                    A B
                8 9 A B
                        C D E F
                        C D
                            E F
                        C D E F
                8 9 A B C D E F
0 1 2 3 4 5 6 7 8 9 A B C D E F

Now add to that the O(n) cost of sorting each partial list, and you've got the classic O(n * logn) complexity.

This question has already been answered. Start a new discussion instead.