AbstractIn 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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).