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)?

2
Contributors
1
Reply
3
Views
7 Years
Discussion Span
Last Post by Momerath
0

Traversing a linked list in an O(n) operation. So splitting a list is an O(n) operation. Having to do it multiple times gives O(n) + O(n/2) + O(n/4), etc. which is still considered O(n). Then it needs to make (n ⌈lg n⌉ - 2⌈lg n⌉ + 1) comparisons. Since we really only care about the part that gives the largest result ([n lg n] will grow faster than [2 lg n]) we end up with O(n) + O(n lg n), which is reduced to O(n lg n).

Wikipedia has more math about it if you want to read it.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.