A Fast Merging Algorithm

Mark R. Brown, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

69 Scopus citations


An algonthm that merges sorted hsts represented as height-balanced binary trees 1s given If the hsts have lengths m and n [formula omitted] then the merging procedure runs m O(m log(n/m)) steps, which is the same order as the lower bound on all companson-based algorithms for this problem.

Original languageEnglish (US)
Pages (from-to)211-226
Number of pages16
JournalJournal of the ACM (JACM)
Issue number2
StatePublished - Apr 1 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence
  • Information Systems
  • Control and Systems Engineering
  • Hardware and Architecture


  • 2-3 tree
  • AVL tree
  • height-balanced tree
  • linear list
  • merging


Dive into the research topics of 'A Fast Merging Algorithm'. Together they form a unique fingerprint.

Cite this