Merge Sort Concept Understanding

Question

Merge Sort contains basically two important routines:

(i) split (ii) merge.

I get the general idea. But I dont understand how this is more efficient than some random bad sort algorithm, like selection sort, for example. I kind understand the maths behind, I know why one is O(n*lg(n)) and the other is O(n²). I know lg32 is 5, and the tree is going to have 5 levels. But in practical terms I don't see the difference. Ok... let me explain how my mind is weirdly thinking.

Let's say we have an array with 32 numbers. Using merge sort, we have to use the split routine 31 times.

(32 -> 16) (1x)

(16-> 8) (2x - split 2 arrays of 16 elements into 4 arrays of 8 elements)

(8-> 4) (4x - split 4 arrays of 8 elements into 8 arrays of 4 elements)

(4 -> 2) (8x)

(2 -> 1) (16x)

Total: 31 splits. Then, we should use the merge routine which is O(n). So, in the end,it's basically 31* n (31 splits multiplied by n - which is the merge routine cost) , so thinking about the total cost of the algorithm is almost n*n...

The only advantage that I see with merge sort is that it can be easily parallelized, there is a huge time efficiency there. But in terms of overall work, I don't see much difference. If parallelization was not allowed, merge sort would still perform better than selection sort for large datasets?

Answer 1

You are miscounting.

The cost to split and merge each sub-array at each level is not O(n), because each of those sub-arrays are getting smaller and smaller. The cost of all the splits and merges at each level is O(n), because each element is touched twice (once in a split, and once in a merge).

E.g.

(32 -> 16) 1x O(32) = O(32)
(16 -> 8) 2x O(16) = O(32)
(8 -> 4) 4x O(8) = O(32)
(4 -> 2) 8x O(4) = O(32)
(2 -> 1) 16x O(2) = O(32)

Total is O(32 * log2(32))

Answer 2

It does not matter how many times you "split" each array. It matters how many times you have to access each item relative to overall input (n).

You actually described well the "split routine". As you can see, for 32 numbers there are 6 splits (your 6 lines), each time you have to go through all numbers. So its 6*32 = 192 steps

The merge is identical as split, just in another direction, so again 6*32=192 steps

Therefore you can merge 32-long array in 192+192=384 steps.

On the other hand selection sort will take 32+31+30+...+2 steps, which is n(n-1)/2 = 496

Now 384 and 496 might look as not that big difference, but that is the point of O-complexity. The difference with small number of items (n) can be neglible. Or if there is some constants, for small-enough number of inputs, the alghoritm with better O-complexity can be even more expensive (i.e. 100*n vs n^2, the 100*n alghoritm which has O(n) complexity is less expensive only for n>100).

If we think about 1024 numbers and those two algorithms above, you get 11*1024*2=22 528 steps with merge sort and 1024*1023/2=523 776 steps with selection sort.

Answer 3

You split an array with 32 elements. Then you split two arrays with 16 elements, then four arrays with 8 elements, eight arrays with four elements, and 16 arrays with two elements.

Each level has n operations, either 1xn, or 2 x (n/2), or 4 x (n/4) and so on, so the total is 5n operations for splitting.