A Linear Time Algorithm for Ordered Partition

DOI10.1007/978-3-319-19647-3_9zbMath1407.68120OpenAlexW1167245303MaRDI QIDQ3452555

Yijie Han

Publication date: 12 November 2015

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19647-3_9

zbMATH Keywords

algorithmssortingperfect hash functionshashinglinear-time algorithmordered partitioninteger sorting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items (2)

Construct a perfect word hash function in time independent of the size of integers ⋮ Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space

Cites Work

• Upper bounds for sorting integers on random access machines
• Sorting in linear time?
• Time bounds for selection
• Expected Linear Time Sorting for Word Size Ω(log2 n loglogn)
• A Reliable Randomized Algorithm for the Closest-Pair Problem
• Priority queues: Small, monotone and trans-dichotomous
• Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs
• Deterministic sorting in O(nloglogn) time and linear space
• Conservative algorithms for parallel and sequential integer sorting

This page was built for publication: A Linear Time Algorithm for Ordered Partition