Abstract
In the summer '85 issue of SIGACT News, N. Santoro enquired about the space-time complexity of unmerging. Suppose that lists A and B, each of size n/2, are merged to produce the list L. The problem is to separate L into A and B in their original order. By studying a simple, but non-optimal stable merging algorithm, we obtain an unmerging algorithm which, using extra space 0(k), runs in unmerging algorithm which, using extra space 0(k), runs in time 0(nlOgkn). Thus, given c > 0, the algorithm can unmerge in linear time provided 0(n') space is available; if only 0(logn) extra space can be used, the algorithm will need 0(niogn/(Ioglogn)) time.