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