# Element-wise merging and re-sorting lists of sorted elements

Imagine you have a vector of pairs $(id, x)$ where $id \in I$, some set of opaque identifiers (hereafter, ids), and $x \in \mathbb{N}$ some value. Assume that every $id$ value is unique in your list. You can sort such a list on the $x$ values - below we will generally refer to this as a sorted list.

Given two such sorted lists $l_1, l_2$, I'm interested in merging and re-sorting the lists. Assume for now that the two lists both have length $s$, and the set of $id$ values appearing in $l_1$ is equal to the set appearing in $l_2$, and denote this set as $D$.

My merging I mean creating a merged list $l_m$, of the same length as $l_1$ and $l_2$, which has as its elements $(a, x_1 + x_2)$ where $x_1$ and $x_2$ are the corresponding values from the element $(a, x)$ with the same id $a$ in $l_1$ and $l_2$ respectively.

The the re-sorting simply involves sorting the merged list by its value in the same way as the input lists.

So really it's simple: take a two lists of integer values tagged by some id, add the values for corresponding ids to get a single list and sort it, quickly. That last part is the key - I don't want to throw away all the information already in the two sorted input lists and just sort the merged lists from scratch.

Since you already have the two sorted input lists, you can put some bounds on the position of many of the elements in the final list. For example, if a given id appears in position $j$ in the first list and position $k$ in the second list, then it must appear no later than position $j + k$ in the sorted list (of course, this bound is useful only for the elements where $j + k < s$). A similar bound applies for the position of each element measured from the end of the list - the element must appear in the last $2s - j - k$ elements of the list.

Are those bounds helpful in sorting the list? Better bounds can be calculated on the fly after examining some elements from the top of the list, but it's not clear to be how to use it.

I'm interested both in the case where the $id \leftrightarrow value$ relationship is uncorrelated, but also especially in the case where there is a correlation between them across the input lists (i.e., ids with large (small) values in $l_1$ are more likely to have large (small) values in $l_2$). That correlation holds in many real word data sets.

It seems like this type of operation would be common for any type of distributed query and sorting system. For example, imagine a system which records of the form $(string, value)$, much like the tuples above, except that each $string$ could appear many times, and you want to issue a query to return all unique strings, along with the sum of all their values for each string (this is just a select string,sum(values) group by string type query in a database). With distributed record storage, you'd expect a list of already-sorted tuples coming back just as described above, and your reduce step should merge and re-sort as described$^1$.

$^1$ Of course, you could argue that you simply don't sort the partial results from each distributed node, since it may be better simply to merge and then do a final sort once the results are reduced across all nodes - but this ignores the fact that reduce time is more valuable than distributed calculated time, since only the latter is effectively parallelizable. So you want to push as much work as possible to the distributed calculation, including the sort.