Expected Linear Time Sorting for Word Size Ω(log2 nloglog n)

Djamal Belazzougui, Gerth Stølting Brodal, and Jesper Sindahl Nielsen

In Proc. 14th Scandinavian Workshop on Algorithm Theory, volume 8503 of Lecture Notes in Computer Science, pages 26-37. Springer Verlag, Berlin, 2014.

Abstract

Sorting n integers in the word-RAM model is a fundamental problem and a long-standing open problem is whether integer sorting is possible in linear time when the word size is ω(log n). In this paper we give an algorithm for sorting integers in expected linear time when the word size is Ω(log2 n log log n). Previously expected linear time sorting was only possible for word size Ω(log2+ε n). Part of our construction is a new packed sorting algorithm that sorts n integers of w/b-bits packed in O(n/b) words, where b is the number of integers packed in a word of size w bits. The packed sorting algorithm runs in expected O(n/b(log n + log2 b)) time.

Copyright notice

© Springer International Publishing Switzerland 2014. All rights reserved.

Online version

swat14sort.pdf (348 Kb)

DOI

10.1007/978-3-319-08404-6_3

Links

BIBTEX entry

@incollection{swat14sort,
  author = "Djamal Belazzougui and Gerth St{\o}lting Brodal and Jesper Sindahl Nielsen",
  booktitle = "Proc. 14th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/978-3-319-08404-6_3",
  isbn = "0302-9743",
  pages = "26-37",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Expected Linear Time Sorting for Word Size $\Omega(\log^2 n\log\log n)$",
  volume = "8503",
  year = "2014"
}