AbstractN. Santoro inquired about Y ose that two-sorted lists A the space-time complexity N of unmerging. Suppose A and B, each of size n ' 12 are merged to produce the list L. The problem is to separate L into A and B in sorted order. An optimal algorithm is presented which unmerges in time 0(n) using 0(i) extra space, and which is stable.
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).