1
$\begingroup$

I am wondering if we had a large array to sort (let's say 1,048,576 random integers), chosen because it is a perfect power of 2, if we can just keep dividing those blocks into smaller and smaller half size blocks, how would someone know (on a particular computer using a particular language and complier) what the ideal blocksize would be to get the best actual runtime speed using mergesort to put them all back together? For example, what if someone had 1024 sorted blocks of size 1024, but it could that be beaten by some other combination? Is there anyway to predict this or someone has to just code them and try them all and pick the best? Perhaps for simplicity they would want to use some simple bubblesort on the 1024 size blocks, then merge them all together at the end using mergesort. Of course the mergesort portion would only work on 2 sorted blocks at a time, merging them into 1 larger sorted block.

Also, what about the time complexity analysis on something like this? Would all divide and conquer variations of this be of the same time complexity? The 2 extremes would be 2 sorted blocks (of size 524,288) or 1,048,576 "sorted" blocks of size 1, handed over to a merge process at that point.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The normal way to tell is through measurement: we try different choices for the threshold, benchmark each one, and choose the best. This can be tricky, as the best threshold might vary from computer to computer (depending on, e.g., the relative speeds of CPU vs RAM, the size of various caches, and so on). So, a plausible approach might be to benchmark on multiple different platforms and then choose one threshold that seems to do ok on most of them.

Asymptotic running time analysis probably won't be very helpful, because the constants matter a lot; and because the cache/memory hierarchy probably matters a lot, and standard running time analysis doesn't model the memory hierarchy very well.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @D. W. - Yes I agree, in some cases some sorting algorithms that are expected to do well don't do so well because of memory page faults when they try to access radically different parts of the array to be sorted very close in time to each other, whereas some sorting algorithms that reference "neighbors" a lot do well with data caching. $\endgroup$
    – David James
    Commented Apr 19, 2020 at 22:31
  • $\begingroup$ I guess to get the "absolute" speed difference of 2 different sorting algorithms, you might have to turn off ALL caching (if that is even possible), such as CPU and data caching, then somehow record how long it takes (in clock cycles), to run a particular block of code. If you know that, then perhaps you can have the computer count up how many times each block is executed and then get a total running time. I doubt it would be totally accurate because a block of code could have different times depending on which if statement are executed so sadly, maybe there is no perfect way to do this. $\endgroup$
    – David James
    Commented Apr 19, 2020 at 22:39
  • $\begingroup$ @DavidJames, there may not be much point in measuring the performance with caching turned off, because what we actually care about is the performance when caches are turned on. Turning off caches before measuring performance would be a bit like looking for your lost keys at night under the lamppost because that's where the light is. $\endgroup$
    – D.W. ♦
    Commented Apr 19, 2020 at 23:26
  • $\begingroup$ But if we want to count clock cycles then that is useful. Just like it is useful to check how many comparisons it takes different sorting algorithms to work their "magic". Yes I agree actual runtime is important in judging efficiency, but if there are some tweaks to make some sorting algorithms not have to work as hard, that is likely a good thing. Even with caching on, an inefficient algorithm will still show bad relative results (slow bubblesort vs. faster heapsort for example on a medium size array of numbers). I would expect heapsort to be faster in all but a few extreme cases. $\endgroup$
    – David James
    Commented Apr 19, 2020 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.