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