How complexity of merge sort is o(nlogn)

Question

I understood the concept of merge sort. But I am having the hard time in analyzing the time complexity of merge sort. I know it is o(n log n) for all the cases i.e. for worst case, avg case and best case. But I am not able to understand how it is o(n log n). At every iteration we will be dividing the list twice. So it is more like increasing the recursive calls at every step. So how it will be o(n log n).

Can any one please explain it and also can you please explain o(log n)?

Answer 1

Think of it like sorting a 128 sheets of paper with numerals written on them. The first step is to arrange adjacent sheets. You have to touch/move all 128 sheets to do that. The next step is to merge pairs into groups of four. Again you need to move all 128 sheets to do that. Then you make groups of 8, groups of 16, groups of 32, groups of 64 and finally a group of 128. In each step you have to move all 128 sheets. You'll notice there are 7 levels overall. This is log(128). Therefore you move 128 sheets at 7 levels, or O(128*7) i.e. O(n log n).

• Step 1. Arrange 128 individual sheets as 64 pairs of sheets
• Step 2. Arrange 64 pairs of sheets into 32 sorted groups of 4
• Step 3. Arrange 32 groups of 4 into 16 groups of 8
• Step 4. Arrange 16 groups of 8 into 8 groups of 16
• Step 5. Arrange 8 group of 16 into 4 groups of 32
• Step 6. Arrange 4 groups of 32 into 2 groups of 64
• Step 7. Arrange 2 groups of 64 into 1 final group of 128