Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Radix Sort

Sorting Algorithm

A non-comparison sort that sorts integers or fixed-length strings by processing one digit or character position at a time, from least to most significant, achieving linear time in the number of elements when the key length is bounded.

Facts
Time Complexity
O(d*n), where n is the number of keys and d is the key length in digits 2
Credited To
Herman Hollerith 2
Time Complexity
Time Complexity (category)
Linear Time -- O(n) 1
Connections

Credited To

Herman Hollerith, Pioneers
Source Wikipedia: Radix sort

In Field

Algorithms and Complexity Theory, Fields

Invented By

Herman Hollerith, Pioneers
Source Wikipedia: Radix sort
Sources
1. Radix Sort (Wikipedia)
Wikipedia infobox: time complexity linear
Quote, Wikipedia infobox: time complexity linear
linear
View the Source
2. Wikipedia: Radix sort
  • Complexity and performance
    Radix sort operates in O(d·n) time, where n is the number of keys, and d is the key length in digits.
  • History
    Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.
  • Invented By: Herman Hollerith, History section
    Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.
  • Credited To: Herman Hollerith, History section
    Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.
  • In Group: Distribution and Integer Sorting Algorithms, Lead section
    non-comparative sorting algorithm
View the Source
Wikidata: Radix Sort
Wikidata Q830223, class allow-list match (w-wdresolver-0926)View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.