# Why is mege sort O(n log n)?

Discussion in 'C' started by Whilliam, Oct 5, 2010.

1. ### WhilliamNew Member

Joined:
Oct 5, 2010
Messages:
1
0
Trophy Points:
0
Example, n is 8.
Merge sort (for link list) is constantly divide the list into two sublist until every node->next will point to null. Then, sort them by merging them.

When I tried to count it myself, in the divide part
first divide the 8 nodes into two. In link list, you will need to traverse. Since traversing in merge sort is n/2, I will have 4 traversals.
After dividing the 8 nodes into two, I will divide the left sublist (which has 4) and the right sublist (which also has 4) into two. The left sublist will have 2 traversal, as well as the right sublist.
Sum it all up, it will be O(8).
Then, divide the 4 groups of 2 into half, we will add 4 to O(8).
So technically, it's O(12) in the divide part.
Then in the merge part, it's actually the same.
So it should be O((n + 4)*(n + 4)).
Can anyone explain to me why merge sort is O(n log n)?

Joined:
Dec 20, 2009
Messages:
572