When can we sort in \(o(n\log n)\) time?
type: Item
instance of: scholarly article
title: When can we sort in \(o(n\log n)\) time?
zbMATH Open document ID: 0878.68059
author: Amir M. Ben-Amram
author: Zvi Galil
published in: Journal of Computer and System Sciences
publication date: 1997-08-03T00:00:00Z
Mathematics Subject Classification ID: 68P20
zbMATH DE Number: 1022059
zbMATH Keywords: random access machine
MaRDI profile type: Publication
full work available at URL: jcss.1997.1474
OpenAlex ID: W1964765091
cites work: On the computational power of pushdown automata
cites work: Hash functions for priority queues
cites work: Organization and maintenance of large ordered indexes
cites work: On pointers versus addresses
cites work: On the complexity of functions for random access machines
cites work: Surpassing the information theoretic bound with fusion trees
cites work: Upper bounds for sorting integers on random access machines
cites work: Q4057549
cites work: On parallel hashing and integer sorting
cites work: Q3940846
DOI: 10.1006/JCSS.1997.1474
Recommended article: Can We Overcome the n log n Barrier for Oblivious Sorting?
Recommended article: Sorting in Average Time $o(\log \,n)$
Recommended article: Sorting in linear time?
Recommended article: Q4234091
Recommended article: INSERTION SORT is \(O(n \log n)\)
Recommended article: Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
Recommended article: Deterministic sorting in O(nloglogn) time and linear space
Recommended article: Expected Linear Time Sorting for Word Size Ω(log2 n loglogn)
Recommended article: An in-place sorting with O ( n log n ) comparisons and O ( n ) moves
description: scientific article; zbMATH DE number 1022059