Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations

DOI10.1006/jagm.2002.1211zbMath1002.68038OpenAlexW2024305877WikidataQ56066266 ScholiaQ56066266MaRDI QIDQ4538079

Mikkel Thorup

Publication date: 11 July 2002

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.2002.1211

zbMATH Keywords

dictionariespriority queuesrandomized sorting algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10) Randomized algorithms (68W20)

Related Items (10)

Oblivious RAM with \textit{worst-case} logarithmic overhead ⋮ Faster Fully-Dynamic Minimum Spanning Forest ⋮ Sorting Short Keys in Circuits of Size ${o(n \log n)}$ ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ Oblivious RAM with worst-case logarithmic overhead ⋮ Value-at-Risk model for hazardous material transportation ⋮ Compressed subsequence matching and packed tree coloring ⋮ Subquadratic algorithms for 3SUM ⋮ Group testing: Revisiting the ideas

This page was built for publication: Randomized Sorting in O(nloglogn) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations