Yugodocs

Merge Sort - ping pong merges

The top down merge sort wiki example does the equivalent of this, changing the direction of merge with the level of recursion, doing a one time copy. The bottom up example suggests this by swapping pointers rather than a copy back. For bottom up, the number of passes can be calculated in advance and if odd, pairs can be swapped in place so that the first pass starts off with runs of 2. This could be generalized to use insertion sort of 16 or 64 elements at a time for even number of passes, 32 elements at a time for odd number off passes, so that an even number of merge sort passes occurs. Rcgldr (talk) 13:48, 24 December 2022 (UTC)