Stable unmerging in linear time and constant space

Jeffrey S. Salowe, W. L. Steiger

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)285-294
Number of pages10
JournalInformation Processing Letters
Volume25
Issue number5
DOIs
StatePublished - Jul 10 1987

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Merge
  • optimal space
  • optimal time
  • sorting
  • stable
  • unmerge

Fingerprint

Dive into the research topics of 'Stable unmerging in linear time and constant space'. Together they form a unique fingerprint.

Cite this