4 ms·
My favorite problem involving Two Sorted Integer Lists is "Sort X+Y": Given sorted lists X and Y, each of length N, produce the list of N^2 pair-sums in sorted
by rav 5y ago
My favorite problem involving Two Sorted Integer Lists is "Sort X+Y": Given sorted lists X and Y, each of length N, produce the list of N^2 pair-sums in sorted order. Specifically X+Y is the set {a + b for a in X and b in Y}. It seems like you should be able to solve it without relying on a sorting algorithm, since the input lists are already sorted. However, it's unknown if there is a faster algorithm than simply constructing X+Y directly and running a sorting algorithm.
- deleted 5y ago[deleted]
- whatshisface 5y agoProduce 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.
- bobthepanda 5y agoCouldn’t you construct a list of lists, where each is the output of one entry x + Y, and then just merge those lists like one would merge two sorted lists? (Basically just popping off the smallest head at any given time) You need to do the construction anyways (after all you need the elements of X+Y and you can’t get them without summing)
- karpierz 5y agoYou end up with N lists to merge, so to find the smallest head at each given time, you'd take log(N) steps. Given that you have N^2 elements, it would take a total of N^2 log(N) time, which is equivalent in time complexity to simply sorting a list with N^2 elements.
- bobthepanda 5y agoHm. that's fair. Just append them altogether and apply timsort, I guess, or some other sort that identifies runs well.
- comex 5y agoHmm… what do you mean by faster? I guess you must mean something more nuanced than big-O. From a big-O perspective, sorting is typically O(n log n), but any algorithm that outputs n^2 values must take at least O(n^2) time, so adding O(n log n) makes no difference.
- kadoban 5y agoThe size of the output is n^2. So you do need at least that much effort. But it's not O(n lg n) to sort n^2 items, it'd be O(n^2) to just construct the output and then O(n^2 lg n) to sort it. So there is potentially a lg n to shave off there.