Munro–Paterson algorithm

GPTKB entity

Statements (16)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
gptkbp:complexity O(n log k)
gptkbp:designedFor selection in read-only memory
gptkbp:doi 10.1016/0022-0000(80)90002-4
gptkbp:field computer science
selection algorithm
https://www.w3.org/2000/01/rdf-schema#label Munro–Paterson algorithm
gptkbp:introducedIn 1980
gptkbp:namedAfter gptkb:J._Ian_Munro
Mike S. Paterson
gptkbp:notableFor finding the k-th smallest element in read-only memory with limited workspace
gptkbp:publishedIn gptkb:Journal_of_Computer_and_System_Sciences
Selection and Sorting with Limited Storage
gptkbp:spaceComplexity O(k)
gptkbp:bfsParent gptkb:J._Ian_Munro
gptkbp:bfsLayer 7