Stable unmerging in linear time and constant space
JS Salowe, WL Steiger - Information Processing Letters, 1987 - Elsevier
In the Summer 1985 issue of SIGACT News, Santoro enquired about the space-time
complexity of unmerging. Suppose that two sorted lists A and B of total size n 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 O (n) time using O (1) extra space, and which is
stable.
complexity of unmerging. Suppose that two sorted lists A and B of total size n 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 O (n) time using O (1) extra space, and which is
stable.