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)?
For better explanation use this link:- http://lcm.csa.iisc.ernet.in/dsa/node7.html or this link:- http://wiki.answers.com/Q/How_do_you_calculate_time_complexity_for_merge_sort
