2 ms·
Produce N sorted lists by adding each element in X to the elements of Y. Then mergesort them. Since the blocks you're starting with are runs than one element, y
by whatshisface 5y ago
Produce N sorted lists by adding each element in X to the elements of Y. Then mergesort them. Since the blocks you're starting with are runs than one element, you're guaranteed to save the last few (log2 N) steps of recursion. That's faster, although it only a constant factor.