# Expected Linear Time Sorting for Word Size Ω(log^{2} *n*loglog *n*)

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 Ω(log^{2} *n* log log
*n*). Previously expected linear time sorting was only possible for
word size Ω(log^{2+ε} *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* + log^{2} *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**

**BIBT**_{E}X 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"
}