Aarhus University Seal

Expected linear time sorting for word size Ω(log2 n log log n)

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Djamal Belazzougui, University of Helsinki, Unknown
  • Gerth Stølting Brodal
  • Jesper Asbjørn Sindahl Nielsen, Denmark

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 Ω(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.

Original languageEnglish
Title of host publicationAlgorithm Theory – SWAT 2014 : 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings
EditorsR. Ravi, Inge Li Gørtz
Number of pages12
PublisherSpringer VS
Publication year1 Jan 2014
ISBN (print)9783319084039
Publication statusPublished - 1 Jan 2014
EventScandinavian Symposium and Workshops on Algorithm Theory - Copenhagen, Denmark
Duration: 2 Jul 20144 Jul 2014
Conference number: 14


ConferenceScandinavian Symposium and Workshops on Algorithm Theory
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 81804854