Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations

No abstract is available for this paper.

• Publication year

  1997

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  1997-01-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1006/jagm.2002.1211
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds

  1997cited by this paper
• On RAM priority queues

  1996cited by this paper
• Fast Algorithms for Shortest Paths and Sorting

  1996cited by this paper
• Static Dictionaries on Ac 0 Rams: Query Time ( R Log N= Log Log N) Is Necessary and Suucient

  1996cited by this paper
• Static Dictionaries on RAMs: Query Time is Necessary and Sufficient

  1996cited by this paper
• Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication

  1996cited by this paper
• Priority Queues: Small, Monotone and Trans-dichotomous

  1996cited by this paper
• Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes

  1996cited by this paper
• Radix Sorting & Searching

  1996cited by this paper
• Sorting in linear time?

  1995influential reference
• A new efficient radix sort

  1994cited by this paper
• Surpassing the Information Theoretic Bound with Fusion Trees

  1993cited by this paper
• Improved parallel integer sorting without concurrent writing

  1992cited by this paper
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths

  1990cited by this paper
• Optimal bounds for decision problems on the CRCW PRAM

  1989cited by this paper
• Optimal bounds for decision problems on the CRCW PRAM

  1987cited by this paper
• Universal Classes of Hash Functions

  1979cited by this paper
• Preserving order in a forest in less than logarithmic time

  1975cited by this paper
• A characterization of the power of vector machines

  1974cited by this paper
• Vergleich der hypergeometrischen mit der Binomial-Verteilung

  1966cited by this paper
• A note on two problems in connexion with graphs

  1959cited by this paper

• SIGACT News Online Algorithms Column 41: 2023 in review

  2023cites this paper
• Oblivious RAM with Worst-Case Logarithmic Overhead

  2023cites this paper
• Sorting Short Keys in Circuits of Size ${o(n \log n)}$

  2022cites this paper
• Enhancement of Bubble and Insertion Sort Algorithm Using Block Partitioning

  2022cites this paper
• Optimal Sorting Circuits for Short Keys

  2021cites this paper
• Group testing: Revisiting the ideas

  2021cites this paper
• Bounded Suboptimal Token Swapping

  2020cites this paper
• Approximating text-to-pattern Hamming distances

  2020cites this paper
• Sorting Short Keys in Circuits of Size o(n log n)

  2020cites this paper
• Optimal group based testing strategy for detecting infected individuals: comparison of algorithms

  2020cites this paper
• Simulating competitiveness and precision in a tournament structure: a reaper tournament system

  2019cites this paper
• Conflict Handling Framework in Generalized Multi-agent Path finding: Advantages and Shortcomings of Satisfiability Modulo Approach

  2019cites this paper
• Can We Overcome the n log n Barrier for Oblivious Sorting?

  2019influential citation
• Multi-agent Path Finding with Generalized Conflicts: An Experimental Study

  2019cites this paper
• Agents and Artificial Intelligence: 11th International Conference, ICAART 2019, Prague, Czech Republic, February 19–21, 2019, Revised Selected Papers

  2019cites this paper
• Foundations of Differentially Oblivious Algorithms

  2019cites this paper
• Finding Optimal Solutions to Token Swapping by Conflict-Based Search and Reduction to SAT

  2018cites this paper
• A comparison-free sorting algorithm on CPUs and GPUs

  2018cites this paper
• Lazy Modeling of Variants of Token Swapping Problem and Multi-agent Path Finding through Combination of Satisfiability Modulo Theories and Conflict-based Search

  2018cites this paper
• An Efficient O( $N$ ) Comparison-Free Sorting Algorithm

  2017cites this paper
• IMPLEMENTATION OF PREVIOUS AND IMPROVED BUBBLE AND SELECTION SORT ALGORITHMS WITH THEIR COMPARISON

  2017cites this paper
• Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance

  2017cites this paper
• Improved Double Selection Sort using Algorithm

  2017cites this paper
• Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back

  2017cites this paper
• Reaper Tournament System

  2017cites this paper
• A COMPARISON-FREE SORTING ALGORITHM ON CPUs

  2016cites this paper
• QUINSERTION: A HYBRID SORTING TECHNIQUE

  2016cites this paper
• An Optimized Input Sorting Algorithm

  2016cites this paper
• Top- Based Adaptive Enumeration in Constraint Programming

  2015cites this paper
• C HAPTER 3 F INGERPRINTS IN C OMPRESSED S TRINGS

  2015cites this paper
• Improve Performance of clustering on Cloud Datasets using improved Agglomerative CURE Hierarchical Algorithm

  2015cites this paper
• Compressed Subsequence Matching and Packed Tree Coloring

  2014cites this paper
• Max Min Sorting Algorithm A New Sorting Approach

  2014cites this paper
• Similarity measures and algorithms for cartographic schematization

  2014cites this paper
• Advanced Optimization of Fundamental Searching and Sorting Algorithms

  2014cites this paper
• Expected Linear Time Sorting for Word Size Ω(log2 n loglogn)

  2014cites this paper
• Faster Fully-Dynamic Minimum Spanning Forest

  2014cites this paper
• Study of Sorting Algorithm to Optimize Search Results

  2013cites this paper
• Value-at-Risk model for hazardous material transportation

  2013cites this paper
• Klee's Measure Problem Made Easy

  2013cites this paper
• Improved Exponential Tree Integer Sorting Algorithm Using Node Growth

  2012cites this paper
• Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance

  2012cites this paper
• Four Soviets Walk the Dog - with an Application to Alt's Conjecture

  2012cites this paper
• Index Sort

  2011cites this paper
• Implementation and Performance Analysis of Exponential Tree Sorting

  2011cites this paper
• Randomized Signature Sort: Implementation and Performance Analysis

  2011cites this paper
• Optimizing Integer Sorting in O ( n log log n ) Expected Time in Linear Space

  2011cites this paper
• IMPROVED EXPONENTIAL TREE INTEGER SORTING ALGORITHM USING NODE GROWTH

  2011influential citation
• IMPROVED RANDOMIZED SIGNATURE SORT: IMPLEMENTATION AND PERFORMANCE ANALYSIS

  2011cites this paper
• IMPROVING PERFORMANCE OF RANDOMIZED SIGNATURE SORT USING HASHING AND BITWISE OPERATORS

  2011cites this paper
• On the Cache Performance of Time-Efficient Sorting Algorithms

  2011cites this paper
• Average Sort

  2011cites this paper
• An Enhancement of Major Sorting Algorithms

  2010cites this paper
• Enhanced Quicksort Algorithm

  2010cites this paper
• Deterministi Sorting in O(n log log n) Time and Linear Spa e 1

  2010cites this paper
• Transdichotomous Results in Computational Geometry, II: Offline Search

  2010cites this paper
• Regular expression matching with multi-strings and intervals

  2010cites this paper
• Selection of Best Sorting Algorithm for a Particular Problem

  2009cites this paper
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time

  2009cites this paper
• Edit Distance Under Block Operations

  2008cites this paper
• Study and Comparison of various sorting algorithms

  2008influential citation
• Voronoi diagrams in n · 2o(√lg lg n) time

  2007cites this paper
• Computational Geometry through the Information Lens by Mihai Pǎtraşcu

  2007cites this paper
• Computational geometry through the information lens

  2007cites this paper
• Subquadratic Algorithms for 3SUM

  2005cites this paper
• Melding priority queues

  2004cites this paper
• Deterministic sorting in O(nloglogn) time and linear space

  2004cites this paper
• Combinatorial power in multimedia processors

  2003cites this paper
• On AC0 implementations of fusion trees and atomic heaps

  2003cites this paper
• Deterministic sorting in O(nlog log n) time and linear space

  2002influential citation
• Integer Sorting in Expected Time and Linear Space

  2002cites this paper
• Equivalence between priority queues and sorting

  2002cites this paper
• Integer sorting in O(n/spl radic/(log log n)) expected time and linear space

  2002cites this paper
• Improved fast integer sorting in linear space

  2001cites this paper
• Improved Shortest Paths on the Word RAM

  2000cites this paper
• New data structures for orthogonal range searching

  2000cites this paper
• Tight(er) worst-case bounds on dynamic searching and priority queues

  2000cites this paper
• Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree

  1999influential citation
• Faster deterministic sorting and priority queues in linear space

  1998cites this paper
• Sorting and Searching on the Word RAM

  1998cites this paper
• Dictionaries on AC 0 RAMs : Query Time

  1997cites this paper
• On sorting strings in external memory (extended abstract)

  1997cites this paper
• Dictionaries on AC 0 RAMs : Query time Θ ( √ log n / log log n ) is necessary and sufficient ∗

  1997cites this paper
• Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds

  1997influential citation
• Sequence sorting in secondary storage

  1997cites this paper
• Polynomial algorithms for nested univariate clustering

  1996cites this paper
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time (cid:3)

  year unknowncites this paper