algorithmsortingdata-structuresmergesorttimsort

TimSort minRun selection. Why is a perfectly balanced merge preferred over imbalanced merge?


In the "computing minrun" section of the TimRun document, it gave a good and a bad example of selecting the minrun for N=2112 array. It states using minrun = 32 is inefficient because

runs of lengths 2048 and 64 to merge at the end The adaptive gimmicks can do that with fewer than 2048+64 compares, but it's still more compares than necessary, and-- mergesort's bugaboo relative to samplesort --a lot more data movement (O(N) copies just to get 64 elements into place).

it also described the minrun = 32 algo as:

then we've got a case similar to "2112", again leaving too little work for the last merge to do

It then stated that choosing minrun = 33 will end up with a perfectly balanced merge which is better.

If we take minrun=33 in this case, then we're very likely to end up with 64 runs each of length 33, and then all merges are perfectly balanced. Better!

My questions are why is merging perfectly balanced sorted arrays better than imbalanced arrays if the total element count is the same(2112 in the example)?

why is minrun=32 "doing more compares than necessary" when the total element is also 2112 for minrun=33?

why is there "more data movement"?

why does the last merge have "too little work to do"?

My understanding is, merging sorted arrays of size A & size B will take O(A+B). Why is it more efficient when A & B are the same size?

I drew diagrams of how the 2 minrun scenarios are executed but I'm still confused.

merge rules

bad min run example

good min run example

calcMinRun function


Solution

  • For 2112 elements if all runs are size 33, then it will take 6 steps to merge from 33 to 2112: 33 -> 66 -> 132 -> 264 -> 528 -> 1056 -> 2112. If all runs are size 32, it will take 7 steps to merge from 32 to 2112: 32 -> 64 -> 128 -> 256 -> 512 -> 1024 -> 2048 -> 2112.

    If you do the math, with minrun = 33, the entire array is processed in 6 steps, with minrun = 32, nearly the entire array (2048 elements) is processed in 6 steps, then the entire array is processed in the 7th step.