Editing Radix sort (section)

== History ==

Radix sort dates back as far as 1887 to the work of [[Herman Hollerith]] on [[tabulating machines]].<ref>{{Cite patent|country= US |number= 395781}} and {{Cite patent|country= UK |number= 327}}</ref> Radix sorting algorithms came into common use as a way to sort [[punched card]]s as early as 1923.<ref name="auto">
[[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89685-0}}. Section 5.2.5: Sorting by Distribution, pp.&nbsp;168–179.
</ref>

The first memory-efficient computer algorithm for this sorting method was developed in 1954 at [[Massachusetts Institute of Technology|MIT]] by [[Harold H. Seward]]. Computerized radix sorts had previously been dismissed as impractical because of the perceived need for variable allocation of buckets of unknown size. Seward's innovation was to use a linear scan to determine the required bucket sizes and offsets beforehand, allowing for a single static allocation of auxiliary memory. The linear scan is closely related to Seward's other algorithm — [[counting sort]].

In the modern era, radix sorts are most commonly applied to collections of binary [[String (computer science)|strings]] and [[Integer (computer science)|integers]]. It has been shown in some benchmarks to be faster than other more general-purpose sorting algorithms, sometimes 50% to three times faster.<ref>{{Cite web|url=https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/|title=I Wrote a Faster Sorting Algorithm|date=28 December 2016}}</ref><ref>{{Cite web|url=https://erik.gorset.no/2011/04/radix-sort-is-faster-than-quicksort.html|title=Is radix sort faster than quicksort for integer arrays?|website=erik.gorset.no}}</ref><ref>{{Cite web|url=https://www.boost.org/doc/libs/1_62_0/libs/sort/doc/html/boost/sort/spreadsort/integer__idm45516074556032.html|title=Function template integer_sort - 1.62.0|website=www.boost.org}}</ref>

[[File:SEACComputer 038.jpg|thumb|An [[IBM card sorter]] performing a radix sort on a large set of [[punched cards]]. Cards are fed into a hopper below the operator's chin and are sorted into one of the machine's 13 output baskets, based on the data punched into one column on the cards. The crank near the input hopper is used to move the read head to the next column as the sort progresses. The rack in back holds cards from the previous sorting pass.]]